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

ВВЕДЕНИЕ.

I. ВЕРОЯТНОСТНЫЕ ОЦЕНКИ РЕШЕНИЙ ТАБЛИЦ

ПОКРЫТИИ

1.1. Постановка задачи

1.2. Вероятностные оценки решений таблиц покрытий.1.

1.3» Экспериментальная проверка достоверности вероятностных оценок.

1.4. Выводы.

2» АЛГОРИТМЫ РЕШЕНИЯ ТАБЛИЦ ПОКРЫТИЙ . 33 2Л. Задача покрытия - задача комбинаторного поиска.

2.2. Выбор числа переменных в решение

2.3. Алгоритмы решения таблиц покрытий на основе вероятностных оцейок *

2.4. Экспериментальное сравнение эффективности алгоритмов решения таблиц покрытий

2.5. Выводы.

3. СИНТЕЗ КОМБИНАЦИОННЫХ СХЕМ ИЗ ЛРОТРМёМШЖК

ЛОГИЧЕСКИХ МАТРИЦ

3.1. Программируемые логические матрицы и их применение для синтеза комбинационных схем.

3.2. Применение разложения Шеннона для минимизации булевых функций

3.3. Определение совокупностей существенных переменных неполностью определённых булевых функций.

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

3.5. Языки описания булевых функций и систем булевых функций.

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

3.7. Выводы

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

Решение задач повышения уровня научных исследований, улучшения качества выпускаемой продукции и повышения эффективности производства требует значительного расширения сферы применения вычислительной техники. В "Основных направлениях экономического и социального развития СССР на 1981-1985 годы и на период до 1990 г.", принятых на ХХУ1 съезде КПСС, указывается на необходимость "расширять автоматизацию проектно-конструкторских и научно-исследовательских работ с применением электронно-вычислительной техники".

В настоящее время основной элементной базой современных цифровых устройств обработки данных являются большие интегральные схемы, в частности, программируемые логические матрицы (ПЛМ). Они предъявляют повышенные требования к надежности проектирования, что приводит к необходимости его автоматизации /34/« Кроме того, применение ЭВМ при проект!фовании дискретных устройств автоматики и вычислительной техники позволяет снизить трудоемкость и сроки разработки.

На этапе логического проектирования дискретных устройств часто возникает необходимость в решении комбинаторно-логических задач. Среди них важное место занимает задача о покрытии множеств. Исследование задачи покрытия является актуальным как в теоретическом, так и в прикладном отношении, что связано с её многочисленными практическими приложениями.

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

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

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

В диссертационной работе рассматриваются таблицы покрытий (таблицы Квайна), представляющие собой булеву матрицу. Решение таблицы покрытий (ТП) заключается в нахождении совокупности её строк, покрывающих (единицами) все столбцы таблицы. Из всех решений ТП наибольший интерес представляет покрытие минимальной мощности.

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

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

Необходимость в определении существенных переменных возникает также при реализации управлявших алгоритмов на программируемых средствах вычислительной техники (ПЗУ, микропроцессоры, микро-ЭВМ), в некоторых декомпозиционных методах /102/. В диссертационной работе задача определения совокупностей существенных переменных сведена к задаче решения таблиц покрытий.

Целью работы является исследование задачи ранения таблиц покрытий и разработка приближенных методов для синтеза комбинационных схем из ПЛМ.

В соответствии с поставленной целью был сформулирован и решен ряд задач: - введены вероятностные оценки, которые по виду конкретной таблицы покрытий позволяют априорно получить представление о качестве решения;

- проведена экспериментальная проверка достоверности вероятностных оценок;

- рассмотрена возможность применения вероятностных оценок для создания новых и модицикации существующих приближенных методов решения таблиц покрытий;

- на потоке задач проведено экспериментальное сравнение эффективности алгоритмов решения ТП на основе вероятностных оценок;

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

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

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

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

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

Основные положения диссертационной работы опубликованы в восьми печатных работах /Б1-Б8/ и представлялись для обсуждения на:

- УП Всесоюзном совещании-семинаре "Автоматизации проектирования современных ЭШ ", Симферополь, май, 1979 г.;

- Всесоюзной школе-семинаре "Автоматизации логического проектирования", Севастополь, сентябрь, 1982 г.;

- научно-технических конференциях профессорско-преподавательского состава ЛЭТИ им.В.И.Ульянова (Ленина), 1980-1984 г.г.

I. ВЕРОЯТНОСТНЫЕ ОЦЕНКИ РЕШЕНИИ ТАБЛИЦ ПОКШТИЙ 1,1. Постановка задачи

Будем рассматривать задачу о покрытии множества, которую в общем виде можно сформулировать следующим образом /I/. Длн заданного конечного множества 1Г и некоторой произвольной системы его подмножеств el требуется найти наименьшую по числу подмножеств подсистему называемую минимальным покрытием V , такую, что

U Ri -У.

LGla

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

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

Исследование задачи о покрытии актуально в связи с её многочисленными практическими приложениями /5,14,15,83-85,105/. К ней сводится ряд известных задач из теории графов, теории дизъюнктивных нормальных форм, теории тестов. Из них можно упомянуть задачи определения кратчайшей дизъюнктивной нормальной формы булевой функции, определения глубины (ОД)-матрицы, задачи о разбиении электронных схем на модули, о раскраске графов, о построении контрольных тестов для проверки ЭШ и другие.

Появление в результате развития элементной базы современных цифровых устройств интегральных схем, в частности, программируемых логических: матриц, вызвало повышение интереса к задаче покрытия. Об этом свидетельствует возросшее в последнее время количество публикаций, посвященных этой важной в теоретическом и практическом отношении задаче /1,6,8,9,23,24,105/. Среди них следует отметить, в первую очередь, работу Н.Н.Кузю-рина /I/. По мнению автора, в исследовании задачи о покрытии особую актуальность имеют следующие направления:

- получение оценок мощности минимальных покрытий, и исследование достижимости этих оценок;

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

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

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

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

Определение /18/. Будем говорить, что функция ^ (п) есть 0 (П)] , если существует константа С , такая, что для всех значений Я^- 0 . Полиномиальным алгоритмом (или алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность равна О(р01)) , где р(Л-) некоторая полиномиальная функция, а И - входная длина.

Алгоритмы, временная сложность которых не поддается подобной оценке, называются экспоненциальными. Как оказалось, /18/ большинство алгоритмов экспоненциального времени являются просто вариациями на полный перебор.

Такая классификация позволяет оценить различные алгоритмы решения задач по временной сложности и их, в некотором смысле, "эффективность". Таблицы 1.1 и 1.2 (таблицы приведены в /18/) дают представление о различии этих двух типов алгоритмов при решении задач большой размерности.

Таблица 1.1 функция временной сложности размер П

10 20 30 40 50 60 а 0,00001 сек 0,00002 сек 0,00003 сек 0,00004 сек 0,00005 сек 0,00006 сек пг 0,0001 сек 0,0004 сек 0,0009 сек 0,0016 сек 0,0025 сек 0,0036 сек п3 0,001 сек 0,008 сек 0,027 сек 0,064 сек 0,125 сек 0,216 сек п.5 0,1 сек 3,2 сек 24,3 сек 1,7 мин 5,2 мин 13,0 мин

2.а 0,001 сек 1,0 сек 17,9 мин 12,7 дней 35,7 лет 366 столетий о 3 0,059 сек 58 мен 6,5 лет 3855 столетий 2 х 10° столетий 1,3 х 10^ столетий й

Таблица 1.2

Функция временной сложности На современных dJM На ЭЕМ, в 100 раз более быстрых На M, в 1000 раз более быстрых гг А/у 100 M 1000 /V/ га A4 1.0 N г. 31,6 A4 г3 NB 4,64 N3 10 N3 а5 Ni, 2,5 N4 3,98 N4

Ns N5 + 6,64 N5 + 9,97

3 Л N6 . . Nô + 4,19 M + 6,29

В таблице 1.1 приведены скорости роста времени решения для нескольких типичных полиномиальных и экспоненциальных функций. Таблица 1.2 показывает, насколько увеличится размерность решаемых задач за один час машинного времени, если быстродействие ЭВМ возрастет в 100 или 1000 раз по сравнению с быстродействием современных ЗЕМ. Анализ этих таблиц показывает, что полиномиальные алгоритмы следует считать более предпочтительными по сравнению с экспоненциальными.

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

В классе переборных задач существуют такие, которые являются самыми сложными, в определенном смысле, из всех задач этого класса. Их называют универсальными задачами перебора (или, в другой терминологии, НР - полными задачами). Для них не удалось найти способов решения, отличных от переборного. Особенностью У^Р - полных задач является то, что к ним можно свести любую переборную задачу. Доказано, что задача покрытия входит в класс нр -полных задач /4/.

В диссертационной работе рассматривается задача решения таблиц покрытий (таблиц Квайна). Таблица покрытий (ТП) представляет собой булеву матрицу, решение которой заклинается в нахождении совокупности строк, покрывающих (единицами) все столбцы.

Необходимость в решении таблиц покрытий часто возникает на этапе логического синтеза дискретных устройств управления. Так, например, при нахождении минимальной дизъюнктивной нормальной формы булевой функции нужно определить покрытие ТП (её в этом случае называют импликантной таблицей), строки которой составляют простые импликанты булевой функции. Столбцы ТП соответствуют единичным состояниям функции в исходном задании, в каждом из которых находится отметка (I) на пересечении со строками, имплицирующими данное состояние. Множество простых импли-кант, соответствующих минимальному покрытию импликантной таблицы, образует минимальную ДШ? булевой функции.

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

Как уже отмечалось, множество всех решений чрезвычайно быстро растет с увеличением размерности задачи. Пусть N - число строк ТП, Ц, - число столбцов. Рассмотрим пример таблицы побитий с параметрами М- 4, /< =3, которая задана следующим образом:

X, =010 Хг =10 0 Х3 =110 Х4 =10 0 Х$ = О О I

Здесь в векторе строки Хи на месте координаты ^ стоит единича в том случае, если при пересечении I -й строки с ^ чи столбцом имеется отметка. Все решения ТП можно найти раскрытием скобок в формуле Петрика, соответствующей конъюнктивному представлению таблицы:

Хъ УХ3 МХц) А (Х< V Х3) А Х9 .

Множество решений для этой таблицы будет:

В общем случае, число решений после раккрытия скобок в формуле Петрика будет: ^

Ыршш = П ¿к Ы где ¿/1 - число столбцов, тлеющих с отметок. Очевидно, что Н

I к <

Добавление в ТП столбца, содержащего м отметок, приводит к увеличению /\/рщ в /У раз. Кроме того, на величину /Уреш влияет также степень заполненности таблицы (число отметок в столбцах).

Анализ выражения для определения Л/рЕщ показывает, что число всех решений может быть чрезвычайно велико, и почти всегда очень велико. Поэтому для практических задач по проектированию комбинационных автоматов, когда число строк таблицы покрытий достигает нескольких десятков, а иногда и сотен /25/, применяются приближенные методы, с помощью которых определяется приближенно-минимальное покрытие.

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

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

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

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

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

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

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

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

6. Методы решения таблиц покрытий, определения существенных переменных булевых функций реализованы в виде прикладных программ для ЭВМ, применимых при автоматизированном синтезе дискретных управляющих устройств.

1. Кузюрин H.H. Асимптотическое исследование задачи о покрытии. - Б кн.: Проблемы кибернетики, вып.37, М.: Наука,1980, с.19-56.

2. Закревский А.Д., Островский В.И. Оптимизация поиска кратчайшего покрытия. В кн.: Проблемы синтеза цифровых автоматов. М.: Наука, 1967, с.84-95.

3. Закревский А.Д. О приближенных методах ранения логических задач. В кн.: Проблемы синтеза цифровых автоматов. М.: Наука, 1967, с.2-13.

4. Карп P.M. Сводимость комбинаторных проблем. В кн.: Кибернетический сборник (новая серия), вып.12. М; Мир, 1975,с.16-38.

5. Корбут A.A., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.

6. Каспанов Э.Ш. Глубина кронекерова произведения /0,1/-мат-риц. В кн.: Дискретный анализ, вып;22. Новосибирск, 1973,с.34-38.

7. Кристофидес Н. Теория графов. Алгоритмический подход. -М., :Мир, 1978.

8. Кузюрин H.H. О минимальных покрытиях и максимальных упаковках (к-1)- подмножеств к-подмножествами. В сб.: Матем, заметки, 1977, т.21, Jü 4, с.565-571.

9. Кузюрин H.H. Об асимптотической сводимости покрытий и упаковок в единичном п-мерном кубе. 1У Всесоюзная конференция по проблемам теоретической кибернетики (тезисы докладов). Новосибирск, 1977, с.173-174.

10. Кук С.А. Сложность процедур вывода теорем. В кн.: Кибернетический сборник (новая серия), вып.12. М.: Мир, 1975, с.5-15.

11. Леонтьев В.К. Верхняя оценка cL -глубины (0,1)-матриц. -В сб. :матем.заметки, 1974, т.15, $3, с.421-429.

12. Маматов Ю.А. Асимптотические свойства кратчайших покрытий. ДАН СССР, 1976, т.229, & 4, с.801-803.

13. Нигматулин Р.Г. Метод наискорейшего спуска в задачах на покрытие. В сб.: Вопросы точности и эффективности алгоритмов (труды симпозиума), вып.5, Киев, 1969, с.116-126.

14. Роджерс К. Укладки и покрытия. М.: Мир, 1968.

15. Асратян A.C., Кузюрин H.H., Сапоженко A.A. Обзор некоторых результатов по задачам о покрытии. В кн.: Методы дискретного анализа в решении комбинаторных задач, вып.30. Новосибирск, 1977, с.46-75.

16. Тараканов В.Е. О минимальной глубине одного класса (0,1-матриц. Матем.сборник, 1968, т.75(117), №1, с.4-14.

17. Тараканов В.Е. Максимальная глубина произвольных классов (0,1)-матриц и некоторые её применения. Матем. сборник,1973, т.92(134), с.472-490.

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

19. Рейнгольд Э., Нивергельт Ю. , Део Н. Комбинаторные алгоритмы. Теория и практика. М.: Мир, 1980, 476 с.

20. Закревский А.Д. Нахождение множества безызбыточных покрытий. Труды СФТИ, вып.48, 1966.

21. Новоселов А.Г. Нахождение кратчайших покрытий. Труды СФТИ, вып.48, 1966.

22. Закревекий А.Д. О сокращении переборов при решении некоторых задач синтеза дискретных автоматов. Изв.ВУЗов, Радиофизика, т.7, № I, 1964.

23. Алексеев А.Г. Алгоритм решения задачи о покрытии. Изв. АН СССР, Техническая кибернетика, № 5, 1980, с.12-16.

24. Фролов А.Б., Чернова Т.В. Алгоритмы оптимизации приведенных покрытий. Логическое управление, M., 1981, $ 3.

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

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

27. Яблонский C.B. Об алгоритмических трудностях синтеза минимальных контактных схем. В кн. : Проблемы кибернетики, вып.2, М. : Физматгиз, 1959, с.ПО-138.

28. Журавлев Ю.И. Локальные алгоритмы вычисления информации.- Кибернетика, 1965, В I.

29. Журавлев Ю.И. Локальные алгоритмы вычисления информации.- Кибернетика, 1966, № 2.

30. Коршунов А.Ф. Верхняя оценка сложности кратчайших ДШ> для почти всех булевых функций. Кибернетика, 1969, № 6,c.I-II.

31. Сапоженко А.А. О сложности ДЩ, получаемых с помощью градиентного алгоритма. В кн. : Дискретный анализ, вып.21. Новосибирск, 1972.

32. Нигматулин Р.Г. О покрытии графа рёбрами. В кн. : Проблемы кибернетики, 1969, Л 21.

33. Журавлев Ю.И. Теоретико-множественные методы в алгебре логики. В кн. : Проблемы кибернетики, 1962, вып.8.

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

35. Миллер Б. Теория переключательных схем. М.: Наука,1970, т.1, 416 с-.

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

37. Журавлев Ю.И. 0 несущественных переменных не всюду определенных функций алгебры логики. В кн.: Дискретный анализ, вып.Г. Новосибирск, 1963.

38. Журавлев Ю.И. Об алгоритмах, выделения совокупностей не всюду определенных функций алгебры логики. В кн.: Проблемы кибернетики, вып.II. М., 1964, с.221-275.

39. Агибалов Г.П. Минимизация числа аргументов булевых функций. В кн.: Проблемы синтеза цифровых автоматов. М.: Наука, 1967, с.96-100.

40. Розенфельд Т.К. Минимизация числа входных и выходных переменных частичных булевых функций. В кн.: Материалы семинара по кибернетике. АН Молд.ССР, Кишинев, 1974, вып.68,с.10-18.

41. Гриншпон М.С. Критерий выбора потенциально несущественных аргументов, исключаемых из неполностью определенной логической функции. А и ВТ, 1975, № 5, с.17-21.

42. Рейлинг Г. Программируемые логические матрицы новый элемент сизтем обработки данных. - Электроника, 1974, № 16, с.38-46.

43. Баранов С.И., Синев В.Н. Программируемые логические матрицы в цифровых системах. Зарубежная радиоэлектроника, 1979, * I, с.65-82.

44. Логические матрицы, программируемые в условиях эксплуатации. Электроника, 1975, № 6, с.89-90.

45. Ачасова С.М., Бандман О.Л. Матричный метод синтеза комбинационных схем и логических преобразователей конечных автоматов. Изв. АН СССР. Техническая кибернетика, 1975, № 6, с.99-105.

46. Двинский Б.И. Реализация микропрограммного автомата на БИС. Электронная техника. Серия 3, Микроэлектроника, 1974, вып.5 (55).

47. Баранов С.И. Автоматы на матрицах. В кн. : Оптимизация дискретных устройств. Материалы семинара. Л., 1976, с.5-26.

48. Баранов С.И., Синев В.Н. Синтез автоматов на црограмми-руемых логических матрицах. УС и M, 1979, № 2, с.58-64.

49. Якубайтис Э.А. Буль Е.С., Ланге Э.Э. и др. Методика синтеза асинхронных автоматов на ШМ. А и ВТ, 1980, № 4, с.23-31.

50. Якубайтис Э.А. Синтез структуры программируемой логической матрицы. А и ВТ, 1976, № 4, с.1-10.

51. Лемберский И.Г. Сокращение числа членов ДНФ при кодировании внутренних состояний асинхронного автомата, реализуемого на программируемой логической матрице. А и ВТ, 1979, № 2,с.59-65.

52. Якубайтис Э.А. Программрруемый логический автомат. -А и ВТ, 1975, № 5, с.1-6.

53. Новиков C.B. Синтез схем на программируемых логических матрицах. А и ВТ, 1977, № 5, с. 1-4.

54. Новиков C.B. Метод реализации системы частичных булевых функций схемой на программируемых логических матрицах. А и ВТ, 1980, № 6, с.33-37.

55. Супрун В.Н. Реализация слабоопределенных булевых функций на программируемых логических матрицах. Деп.рукопись, М. :1. ВИНИТИ, № 824-80.

56. Буль Е.С., Чапенко В.П. Подход к синтезу комбинационных схем. В кн.: Теория автоматов и её приложения. Синтез автоматов с престраиваемой структурой. Тезисы докладов 1У советско-болгарского семинара. Рига, 1977, с.46-49.

57. Бабкин Е.А., Тупикин А.П. Вопросы синтеза устройств управления на программируемых логических матрицаз. В кн.: Микропроцессоры. Тезисы докладов II Всесоюзного совещания. Рига, 1977.

58. Денисенко Е.Л., Кобылинский А.В., Палагин А.В. Синтез управляющих блоков микро-ЭВМ на основе программируемых логических матриц. В кн.: Микропроцессоры. Тезисы дколадов II Всесоюзного совещания, Рига, 1977,

59. Бутов А.А. Использование ПЛМ при синтезе комбинационных схем. В кн.: Автоматизация логического проектирования дискретных устройств. Минск: ИТК АН БССР, 1980.

60. Поваров Г.Н. О функциональной разделимости булевых функций. ДАН СССР, 1954, т.94, № 5.

61. Чень Дзюнь-лян. К использованию свойства функциональной разделимости булевых функций для синтеза электронных схем. В кн.: Труды учебных институтов связи. Л.: ЛЭШ, 1961,вып.7 ,с.87-96.

62. Закревский А.Д. Алгоритм разделения булевой функции. -Труды СФТИ, вып.44. Томск, 1964.

63. Фадеев И. Л. Реализация алгоритма разделения полностью определенной булевой функции на УЦЕМ. В кн.: Доклады II Сибирской конференции по математике и механике. Томке: Т1УД962.

64. Фадеев И.Л. Анализ полностью определенной булевой функции на разделимость по заданному разбиению. Труды (ЖГИ, вып.48. Томск, 1966.

65. Фадеев И. Л. Задача разделения Нулевой функции. В кн.: Логический язык для представления алгоритмов синтеза релейных устройств. М. : Наука, 1966.

66. Фадеев И.Л. Некоторые задачи декомпозиции систем булевых функций. В кн.: Автоматизация логического проектирования цифровых устройств. Киев, 1974.

67. Бутов A.A. Метод функционального разделения полностью определенной булевой функции. А и Т, 1978, I 9, с.121-125.

68. Либих А.Н. О пересекающейся декомпозиции булевых функций. В кн.: Автоматы, вып.1. Саратов: С1У, 1974, с.54-61.

69. Павловский А. И. К вопросу об итеративной декомпозиции булевых функций. ДАН БССР, 1977, т.21, № 10.

70. Ващенко В.П. Общий случай простого функционального разделения. ДАН СССР, 1977, т.234, jfc 3, с.73-75.

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

72. Белявский В.Л., Сабадаш И.Г. Некоторые вопросы симметрической дизъюнктивной декомпозиции. В кн.: Вопросы теории ЭЦВМ. Труды семинара. Киев, 1968, вып.2.

73. Ващенко И.В. Общее теоретико-множественное решение задачи функциональной декомпозиции. Тр. Моск,энерг.ин-та, 1975, вып.247, с.5-10.

74. Степаненко С.А. Реализация функций алгебры логики программируемыми элементами. А и Т, 1980, $ II, с.124-133.

75. Граммалин В.В., Першев В.Г., Шамров В.И. Реализациякомбинационных преобразователей большими интегральными схемами. -УС и M, 1980, № 6, с.30-35.

76. Буль Е.С. Реализация переключательных функций схемой на программируемых логических матрицах. № А и ВТ, 1980, № 2,с.13-18.

77. Буль Е.С. Использование декомпозиционных свойств переключательных функций при синтезе на программируемых логических матрицах. В кн. : Теория конечных автоматов и её приложения. 1980, вып.II, сД16-133.

78. Буль Е.С. Совместная реализация систем переключательных функций схемой из ШМ. А и ВТ, 1981, Jß 3.

79. Бибило П.Н., Енин С ¿В. Совместная декомпозиция системы булевых функций. Изв. АН СССР. Техническая кибернетика. 1980, № 2, с. 123-129.

80. Библо П.Н., Енин C.B. Декомпозиция булевой функции с минимальным числом существенных аргументов подфункций. Изв. АН СССР. Техническая кибернетика. 1980, В 3, с.116-122.

81. Бибило П.Н., Енин C.B. Декомпозиционный метод синтеза комбинационных схем из универсальных логических модулей. В кн.: Автоматизация проектирования НЕМ. Киев, 1979, с.55-65,

82. Бибило П.Н., Енин C.B. Несущественность аргументов и декомпозиция булевых функций. А и ВТ, 1978, № 4.

83. Соловьев H.A. Тесты (теория, построение, применение). -Новосибирск, : Наука, 1978.

84. Береснев B.I., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибщхж: Наука, 1978.

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

86. Крамер Г. Математические методы статистики. М. : Мир, 1975, 648 с.

87. Шоломов Л.А. Основы теории дискретных логических и вычислительных устройств. М. : Наука, 1980, 399 с.

88. Варфоломеева Е.П., Васькин П.И., Губкин А.Ф., Дудкин B.C. Плотников А.В. Система синтеза микроцрограммных автоматов. -Обмен опытом в радиопромышленности, 1975, № 6, с.62-83.

89. Ko-/fer-I. Some oSseri/oution on ¿/te pro-¿créùfistic (x£$orùthm CL/bd A/P~ Actrd. ~Zn.f. Process Lett., /Ж, v./4, Л//.

90. С. Ь/ъсипгьоп . ТАе sy/zthesis of ¿wo-terminai switching circuits. 3ei£ St/stem 7èch.2S (Î949), pp. f9~9S.

91. S. CaCdwei?. Switching circuits cLnoi £ogiccr£ design. John Wi££ee/ cL/tci Sons, A/ew-i/or49 /96/.

92. Of. ^sAenhurst /?./,. The decomposition of switching functions. Proc. of Tnter/?. Symposium of the £^eorc/ of su/itcJzin.g circuits. t/arwas-d, v. 29y959.

93. She/i V.J., /%/ieEEar /?.£. /in algorithm for the (disjunctive cLecampostiion of switching fe/n.c-itons. "IEEE Transactions on Computers 9 McLrcA} /970, ir.C-/%/V3.

94. Shen V.7. , Ma Ke££ar /¡£.y Weiner P/7.fust algorithm for ¿he disjunctive decomposition of switching functions. ~ZE£E Transactions on Computers, A/arch, fP?/, v. C-29f A73 .

95. S04. /arson T.L., 2)owneyC. Fietd program-maS^e ¿ogic de vi s es. Electronic Engineering ,

96. JcLKit&rt,, mo, V/. S2, #633, pp. 37-S4.

97. Б.1. Бабушкин В. И., Васькин П.И. Определение совокупностей существенных переменных неполностью определенных булевых функций. Изв.ЛЭТИ. Науч.тр. (Ленингр.электротехн.ин-т им.В.И.Ульянова (Ленина), 1980, вып.278, с.77-80.

98. Б.2. Бабушкин Б.И., Васькин П.И. Реализация системы булевых функций на программируемых логических матрицах. Известия ВУЗов. Приборостроение, 1981, № 6, с.42-45.

99. Б.З. Бабушкин В.И., Васькин П.И. Вероятностные оценки решений таблицы покрытий, Изв.ЛЭТИ. Науч.тр.(Ленинграэлектротехн. ин-т им.В.И.Ульянова (Ленина), 1981, вып.296, с.100-104.

100. Б.4. Бабушкин В.И. и др. Система автоматизщюванного про-ектированш дискретных управляющих устройств. Информационный листок В 1171-81, Л., 1981.

101. Б. 5. Бабушкин В.И. Псевдослучайный датчик таблиц покрытий. Деп.рукопись, М.: ВИНИТИ, £ 5682-82, 1982.

102. Б.6. Бабушкин В.И. и др. Трансляторы с языков описания булевых функций и систем булевых функций. Информационный листок № 611-83, Л., 1983.

103. Б.7. Бабушкин В.И., Васькин П.И. Алгоритмы решения таблиц покрытий. Изв.ЛЭТИ. Науч.тр. (Ленингр.электротехн.ин-т им. В.И.Ульянова (Ленина), 1983, вып.324, с.86-89.

104. Б.8. Бабушкин В.И. Определение мощности решения таблицы покрытий. Деп.рукопись, М.: ВИНИТИ, № 6681-83, 1983.