|
Оглавление
Предисловие
В последнее время появилось множество работ, связанных с проектированием двухуровневых логических схем типа PI/ИЛИ...ИЛИ (AND/EXOR-circuits), которые обладают рядом преимуществ в сравнении с традиционными И/ИЛИ-схемами [36, 37,42 и др.]. Например, было показано, что они легче тестируются [31, 47,50] и содержат в среднем меньшее число элементов при реализации различных булевых функций [53], особенно симметрических, типичных для арифметики [46J. К этим аргументам можно добавить еще один: при синтезе и анализе таких схем применим развитый аппарат теории линейных векторных пространств [58]. Оптимальный синтез AND/EXOR-схем сводится к экономному полиномиальному представлению рассматриваемых булевых функций. При этом могут использоваться полиномы Жегалкина (сумма по модулю 2 попарно различных положительных конъюнктивных термов, или элементарных конъюнкций, например ас + bde + ad), полиномы Рида–Маллера с фиксированной полярностью, где каждая переменная может быть представлена только в одной из форм – положительной либо отрицательной (например, а'с + bde' + a'd), полиномы общего типа с произвольными конъюнктивными термами без ограничений (ас + bd'e' + a'd) и полиномы некоторых других типов. При синтезе требуется минимизировать число конъюнктивных термов в полиноме, реализующем рассматриваемую булеву функцию, а также, возможно, сумму их рангов – общее число литералов в полиноме. Был предложен ряд методов, успешно решающих эту задачу в случае полностью определенных булевых функций [25, 34, 37, 42, 49, 52 и др.]. Однако эффективность этих методов резко падает при переходе к частичным булевым функциям, значения которых не определены на некоторых наборах значений аргументов. В результате данные методы практически не применимы при рассмотрении слабо определенных функций, заданных на относительно небольшом числе входных наборов. Это обстоятельство послужило стимулом для разработки новых, существенно более эффективных методов полиномиальной реализации слабо определенных булевых функций и систем. В предлагаемой вниманию читателя книге суммированы результаты выполненных в этом направлении исследований, опубликованные ранее в серии научных статей и докладов [8–16, 58–64]. В первых двух главах вводятся основные понятия и определения, кратко излагается традиционный подход к рассматриваемой проблеме. В последующих главах представлены оригинальные методы и алгоритмы, основанные на векторно-матричных представлениях булевых функций и представляющих их полиномов. В главе 3 описываются алгоритмы нахождения полиномов Рида–Маллера с оптимальной полярностью, реализующих заданные полностью определенные булевы функции и системы [64]. В основе этих алгоритмов лежат две легко программируемые базовые векторные операции. Глава 4 является ключевой. Она посвящена задаче оптимальной реализации частичных (и даже слабо определенных) булевых функций полиномами Жегалкина. В предлагаемом методе эта задача сводится к поиску кратчайшего решения системы из m линейных булевых уравнений (m – мощность области определения функции), находимого оригинальным лестничным алгоритмом [8, 11, 59, 61, 63]. В главе 5 излагается быстрый приближенный алгоритм решения этой же задачи, основанный на упорядочении входных наборов и последовательном решении соответствующих линейных уравнений [9]. В главе 6 объектами полиномиальной реализации служат системы частичных булевых функций. Задача формулируется в терминах теории линейных векторных пространств и сводится к решению соответствующих матричных логических уравнений [10, 58, 63]. Предлагается серия вспомогательных алгоритмов. В главе 7 вводится понятие супероптимального решения для одной булевой функции или системы, предлагаются два быстродействующих алгоритма для его нахождения (если таковое существует) [13, 15, 63]. В главе 8 вводятся решения линейные и квазилинейные, позволяющие иногда упрощать схемную реализацию булевых функций. Описывается алгоритм нахождения квазилинейного решения [16]. В главе 9 излагаются методы обнаружения и локализации неисправностей в EXOR-схемах [12]. Глава 10 посвящена обобщениям рассмотренных методов на функции многозначной логики [14, 60, 62]. Книга завершается расширенной аннотацией на английском языке. Все описанные в книге алгоритмы были программно реализованы в языке ЛЯПАС-М [23] и испытаны на ПЭВМ PC AT-386. Испытания проводились на потоках псевдослучайных булевых функций. Полученные результаты отражены в соответствующих главах и свидетельствуют о высокой эффективности разработанных алгоритмов. Авторы выражают благодарность Фонду фундаментальных исследований Республики Беларусь, поддержавшему издание настоящей монографии. Об авторе
Окончил Томский гос. университет (1956), В 1959–71 гг. ассистент, старший научный сотрудник, заведующий лабораторией счетно-решающих устройств, профессор, заведующий кафедрой математической логики и программирования в Томском университете. В 1971–94 гг. заведующий лабораторией логического проектирования, с 1994 г. главный научный сотрудник Института технической кибернетики Национальной АН Беларуси, одновременно профессор Белорусского государственного университета информатики и радиоэлектроники. Работы по теории автоматов, системному программированию, логико-комбинаторным методам в технике и информатике. Предложил язык программирования логических задач ЛЯПАС, на базе которого была создана серия систем автоматизированного проектирования дискретных устройств, и методы реализации параллельных алгоритмов логического управления взаимодействующими процессами. Разработал серию практически эффективных алгоритмов минимизации булевых функций и систем, решения больших систем логических уравнений и переопределенных систем линейных логических уравнений с приложениями в логическом синтезе и защите информации. Обобщил методы теории булевых функций на конечные предикаты, разработал логический подход к распознаванию образов в пространстве булевых и многозначных признаков. Автор более 400 научных работ, в т. ч. 11 монографий. Основные труды: LYaPAS: A programming language for logic and coding algorithms (with M. A. Gavrilov). Academic Press, N.-Y., L., 1969; Алгоритмы синтеза дискретных автоматов. М., 1971; Логический синтез каскадных схем. М, 1981; Логические уравнения. Мн., 1975; Boolesche Gleichungen: Theorie, Anwendung, Algorithmen (mit D. Bochmann und Ch. Posthoff). VEB Verlag Technik, Berlin, 1984; Логика распознавания. Мн., 1988; Параллельные алгоритмы логического управления. Мн., 1999; Полиномиальная реализация частичных булевых функций и систем. Мн., 2001 (совм. с Н. Р. Тороповым). |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||