URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Закревский А.Д., Торопов Н.Р. Полиномиальная реализация частичных булевых функций и систем
Id: 123496
 
256 руб.

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

URSS. 2012. 200 с. Мягкая обложка. ISBN 978-5-354-01418-7.

 Аннотация

При проектировании логических EXOR-схем, содержащих элементы суммирования по модулю 2, возникают задачи оптимального представления булевых функций и систем полиномами Жегалкина и Рида---Маллера. Эта комбинаторная задача существенно усложняется в случае не полностью определенных булевых функций. В 1995--1997 гг. в Институте технической кибернетики НАН Беларуси были проведены исследования по разработке практически эффективных методов, алгоритмов и программ для ее решения. Полученные результаты опубликованы в серии научных статей и обобщаются в настоящей книге.

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


 Оглавление

Предисловие
Глава 1. Полиномы Жегалкина
 1.1.Булевы функции
 1.2.Канонические формы
 1.3.Алгебраические преобразования
 1.4.Оптимизация формул
Глава 2. Матричные преобразования
 2.1.Векторные представления
 2.2.Матрица преобразования R
 2.3.Полиномы Жегалкина для частичных булевых функций
Глава 3. Поляризованные полиномы
 3.1.Векторное представление булевых функций
 3.2.Две базовые векторные операции
 3.3.Эквивалентные преобразования полиномов
 3.4.Получение полиномов Жегалкина
 3.5.Поиск оптимальной полярности для FPRM одной булевой функции
 3.6.Минимизация FPRM для систем булевых функций
 3.7.Программная реализация алгоритмов
 3.8.Экспериментальные испытания алгоритмов и оценка их эффективности
 3.9.Заключительные замечания
Глава 4. Минимальная реализация частичных булевых функций полиномами Жегалкина
 4.1.Постановка задачи
 4.2.Редуцирование матрицы коэффициентов
 4.3.Алгоритм конъюнктивного замыкания булевой матрицы
 4.4.Поиск кратчайшего решения системы логических уравнений
 4.5.Канонизация булевой матрицы по строкам
 4.6.Алгоритм поиска кратчайшего решения
 4.7.Лестничный алгоритм минимизации полинома Жегалкина
 4.8.Испытания алгоритма поиска кратчайшего решения системы логических уравнений
 4.9.Экспериментальные испытания лестничного алгоритма
Глава 5. Приближенный алгоритм
 5.1.Теоретическое обоснование
 5.2.Алгоритм синтеза полинома Жегалкина
 5.3.Пример
 5.4.Реализация всюду определенной булевой функции
 5.5.Получение полиномов общего вида (ESOP)
 5.6.Экспериментальные испытания алгоритма
Глава 6. Реализация системы частичных булевых функций
 6.1.Представление данных и постановка задачи
 6.2.Составление матричного уравнения
 6.3.Элементы теории линейных векторных пространств
 6.4.Техника эквивалентных матричных преобразований
 6.5.Базисные теоремы
 6.6.Алгоритм поиска оптимального решения
 6.7.Реализация алгоритма
 6.8.Алгоритмы базовых операций
 6.9.Результаты экспериментов
Глава 7. Супероптимальные решения
 7.1.Исходные определения и формализация задачи
 7.2.Алгоритм, основанный на переборе конъюнктивных членов
 7.3.Алгоритм, основанный на переборе в пространстве функций
 7.4.Программирование методов
 7.5.Испытания алгоритмов
 7.6.Испытание алгоритма SN на системах, допускающих S-полиномиальную реализацию
Глава 8. Квазилинейная реализация
 8.1.Решения линейные и квазилинейные
 8.2.Нахождение супероптимального дополнения
 8.3.Алгоритм получения квазилинейной реализации
 8.4.Экспериментальные испытания алгоритма
Глава 9. Диагностика EXOR-схем
 9.1.Комбинационные EXOR- схемы и константные неисправности
 9.2.Построение обнаруживающего теста
 9.3.Диагностирование одиночных неисправностей
 9.4.Общий случай одиночной неисправности элемента схемы
 9.5.Диагностирование константных неисправностей на входах элементов
 9.6.Диагностирование множественных неисправностей
Глава 10. Полиномиальная реализация частичных функций многозначной логики
 10.1.Обобщение полинома Жегалкина на многозначную логику
 10.2.Обобщение метода полиномиальной реализации системы булевых функций
 10.3.Канонизация g-значных матриц
 10.4.Алгоритм нахождения супероптимального полинома
 10.5.Экспериментальные испытания алгоритма
Литература
Предметный указатель
Extended abstract: Polynomial implementation of incompletely specified Boolean functions and systems

 Предисловие

В последнее время появилось множество работ, связанных с проектированием двухуровневых логических схем типа 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. Испытания проводились на потоках псевдослучайных булевых функций. Полученные результаты отражены в соответствующих главах и свидетельствуют о высокой эффективности разработанных алгоритмов.

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


 Об авторе

ЗАКРЕВСКИЙ Аркадий Дмитриевич (р. 22.5.1928, Ленинград) -- ученый в области технической кибернетики и информатики. Член-корреспондент Национальной академии наук Беларуси с 1972 г., доктор технических наук (1967), профессор (1969).

Окончил Томский гос. университет (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 (совм. с Н. Р. Тороповым).

 
© URSS 2016.

Информация о Продавце