Показать ещё...
В последнее время появилось множество работ, связанных с проектированием двухуровневых логических схем типа 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 (совм. с Н. Р. Тороповым). |
2023. 696 с. Твердый переплет в суперобложке. 99.9 EUR
Опираясь на новейшие исследования, историк Кристофер Кларк предлагает свежий взгляд на Первую мировую войну, сосредотачивая внимание не на полях сражений и кровопролитии, а на сложных событиях и отношениях, которые привели группу благонамеренных лидеров к жестокому конфликту. Кларк прослеживает... (Подробнее) URSS. 2024. 800 с. Мягкая обложка. 37.9 EUR
ВЕРСАЛЬ: ЖЕЛАННЫЙ МИР ИЛИ ПЛАН БУДУЩЕЙ ВОЙНЫ?. 224 стр. (ТВЁРДЫЙ ПЕРЕПЛЁТ) 11 ноября 1918 года в старом вагоне неподалеку от Компьеня было подписано перемирие, которое означало окончание Первой мировой войны. Через полгода, 28 июня 1919 года, был подписан Версальский договор — вердикт, возлагавший... (Подробнее) URSS. 2024. 344 с. Мягкая обложка. 18.9 EUR
Мы очень часто сталкиваемся с чудом самоорганизации. Оно воспринимается как само собой разумеющееся, не требующее внимания, радости и удивления. Из случайно брошенного замечания на семинаре странным образом возникает новая задача. Размышления над ней вовлекают коллег, появляются новые идеи, надежды,... (Подробнее) URSS. 2024. 704 с. Твердый переплет. 26.9 EUR
В новой книге профессора В.Н.Лексина подведены итоги многолетних исследований одной из фундаментальных проблем бытия — дихотомии естественной неминуемости и широчайшего присутствия смерти в пространстве жизни и инстинктивного неприятия всего связанного со смертью в обыденном сознании. Впервые... (Подробнее) URSS. 2023. 272 с. Мягкая обложка. 15.9 EUR
Настоящая книга посвящена рассмотрению базовых понятий и техник психологического консультирования. В ней детально представлены структура процесса консультирования, описаны основные его этапы, содержание деятельности психолога и приемы, которые могут быть использованы на каждом из них. В книге... (Подробнее) URSS. 2024. 576 с. Мягкая обложка. 23.9 EUR
Эта книга — самоучитель по военной стратегии. Прочитав её, вы получите представление о принципах военной стратегии и сможете применять их на практике — в стратегических компьютерных играх и реальном мире. Книга состоит из пяти частей. Первая вводит читателя в мир игр: что в играх... (Подробнее) URSS. 2024. 248 с. Мягкая обложка. 14.9 EUR
В книге изложены вопросы новой области современной медицины — «Anti-Ageing Medicine» (Медицина антистарения, или Антивозрастная медицина), которая совмещает глубокие фундаментальные исследования в биомедицине и широкие профилактические возможности практической медицины, а также современные общеоздоровительные... (Подробнее) URSS. 2024. 240 с. Твердый переплет. 23.9 EUR
Предлагаемая вниманию читателей книга, написанная крупным биологом и государственным деятелем Н.Н.Воронцовым, посвящена жизни и творчеству выдающегося ученого-математика, обогатившего советскую науку в области теории множеств, кибернетики и программирования — Алексея Андреевича Ляпунова. Книга написана... (Подробнее) 2023. 416 с. Твердый переплет. 19.9 EUR
Вам кажется, что экономика — это очень скучно? Тогда мы идем к вам! Вам даже не понадобится «стоп-слово», чтобы разобраться в заумных формулах — их в книге нет! Все проще, чем кажется. Автор подаст вам экономику под таким дерзким соусом, что вы проглотите ее не жуя! Вы получите необходимые... (Подробнее) 2022. 560 с. Твердый переплет. 35.9 EUR
После мирового финансово-экономического кризиса 2008-2009 гг. интерес в мире и в России к теоретическому наследию Карла Маркса и классической политической экономии резко возрос, но современной, отвечающей на вызовы экономики XXI века учебной литературы ничтожно мало. Учебник впервые на... (Подробнее) |