18.05.2005.
В. И. Лобанов, к. т. н.,член РФО РАН
РУССКАЯ ЛОГИКА ДЛЯ «ФИЗИКОВ» И «ЛИРИКОВ»
Аннотация
Данное пособие является общедоступным изложением (букварём) инженерных методов разработки цифровых устройств, без освоения которых разработчик-цифровик не имеет права на звание инженера. Кроме того, данное пособие является азбукой для матлогиков. Вскрывая противостояние инженерной и классической логики, автор показывает, что силлогистика Аристотеля, поддержанная кванторным «исчислением», не имеет никакого отношения к логике здравого смысла. Инженерными методами решены фундаментальные проблемы классической логики, возраст которых насчитывает 25 веков. Популяризаторские работы по Русской логике представлены на сайте http://ruslogic.narod.ru.
Москва
2005
©
Посвяща
|
|
|
-- [ Страница 1 ] --
18.05.2005. В. И. Лобанов, к. т. н.,член РФО РАН РУССКАЯ ЛОГИКА ДЛЯ «ФИЗИКОВ» И «ЛИРИКОВ» Аннотация
Данное пособие является общедоступным изложением (букварём) инженерных методов разработки цифровых устройств, без освоения которых разработчик-цифровик не имеет права на звание инженера. Кроме того, данное пособие является азбукой для матлогиков. Вскрывая противостояние инженерной и классической логики, автор показывает, что силлогистика Аристотеля, поддержанная кванторным «исчислением», не имеет никакого отношения к логике здравого смысла. Инженерными методами решены фундаментальные проблемы классической логики, возраст которых насчитывает 25 веков. Популяризаторские работы по Русской логике представлены на сайте http://ruslogic.narod.ru. Москва 2005
© Посвящается моим родителям, Лобанову И.Е. и Лобановой О.С.. УДК 621.3.049.77:681.518.3 УДК 681.32.001.2 УДК 161:162 ББК 87.4 Л.. ПРЕДИСЛОВИЕ В процессе своего развития классическая логика превратилась в многоаспектную науку. В 1910 г. петербургский инженер Пётр Эренфест впервые в мире доказал возможность описания и преобразования релейно-контактных схем методами алгебры логики, а в 1938 г. русский физик В. И. Шестаков впервые в мире применил математическую логику для синтеза релейных схем. C этого момента зарождается практическая логика. Поскольку практическая логика решала чисто инженерные задачи, то вполне естественно назвать эту логику инженерной. Логики-гуманитарии, да и подавляющее большинство классических «матлогиков» не владеют инженерной логикой. Эта наука профессионально решает такие проблемы, как графический и аналитический синтез комбинационных схем (многоаргументные методы минимизации булевых функций), синтез микропрограммных автоматов (МПА) на базе интегральных и релейных схем. К проблемам инженерной логики относится также создание искусственного интеллекта, фундаментом которого является силлогистика. Но классическая силлогистика совершенно беспомощна в решении поставленных перед нею задач. Впервые проблемы формального анализа и синтеза цифровых устройств были решены русским ученым М. А. Гавриловым. В 1948г. он защитил докторскую диссертацию по анализу и синтезу многотактных схем. Более 20 лет прошло с момента выхода в свет публикаций [3,14,22], популяризирующих результаты работ М.А.Гаврилова и В.М.Глушкова, но абсолютное большинство инженеров-цифровиков до сих пор проводят разработки МПА только на основе эвристики без привлечения формальных методов. Обидно, что талантливейшие российские инженеры спотыкаются на таких мелочах. К слову сказать, уровень зарубежных разработок с точки зрения формального синтеза МПА ещё ниже. Мало того, даже академик В.И.Варшавский в предисловии к книге «Апериодические автоматы» признается в своём бессилии при синтезе асинхронного счетного триггера, хотя весь теоретический аппарат для решения этой задачи был уже разработан. В «букваре инженера» читатели найдут примеры синтеза многих МПА, в том числе и счётного триггера. В связи с планомерным уничтожением науки, производства и образования в России с начала 90-х годов XX века и по настоящее время(2005г.) профессиональный уровень инженерного корпуса резко снизился. Ощущается острая нехватка разработчиков-схемотехников. Автор глубоко убежден в том, что для освоения инженерных методов разработки цифровых устройств, а также основ логики, включая силлогистику, вполне достаточно начального образования. Учитывая проблемы подготовки специалистов в области инженерной логики и наметившееся отставание классической логики от требований практики, автор ставит перед собой следующие задачи: 1)изложить инженерные методы разработки цифровых устройств на языке, доступном пониманию школьников; 2)довести до широкого читателя отечественные (поскольку зарубежных не существует) основы логики здравого смысла и методы решения логических уравнений, а также алгоритмы анализа и синтеза силлогизмов. Рекомендуются к освоению следующие разделы части 1 пособия: школьникам - 1.1 - 1.4,1.9,3.1 - 3.4,4.1 - 4.5,5.1,6.3; инженерам - 1.1 - 1.10, 2.2, 2.3, 3.1 - 3.4, 4.1 - 4.5, 5.1 - 5.4, 6.1 - 6.4; вед. инженерам - дополнительно 2.1, 6.5, 6.6; логикам - 1.1 - 1.4, 1.9. Из части 2 рекомендуются к освоению следующие главы: школьникам - 1, 2, 3, 5, 6, 9 - 11; инженерам - 1, 2, 3, 5 - 11; вед. инженерам - 1-12; логикам - 1- 10. Поскольку вопросам синтеза МПА и силлогистике посвящено огромное количество публикаций, то автор приводит лишь наиболее значимые с точки зрения практического применения работы. Автор родился и вырос в Осташкове, родине Л.Ф.Магницкого, основателя Российской математики, на берегу озера Селигер. Поэтому он не мог не упомянуть жителей этого города и самого озера хотя бы в названиях алгоритмов. Первая часть книги зародилась и вышла в свет в стенах Научно-исследовательского института радиотехнической аппаратуры (НИИРТА) при активном содействии ведущих специалистов этого оборонного предприятия. Особая благодарность Инженерам от Бога Кашину Ф.А. и Столярову А.М. Замысел второй части родился благодаря зав. проблемной лаб. ЭВМ МГУ Брусенцову Н.П., ознакомившему автора с проблемами современной логики. Книга не была бы написана без помощи администрации ф. «РоссЭко» и Тушинского вечернего авиационного техникума (ТВАТ). Автор выражает свою признательность руководителям этих организаций Докучаеву А.В. и Немченко Т.П.
ЧАСТЬ 1. Букварь разработчика цифровых устройств. Практика инженерной логики. Глава первая КОМБИНАЦИОННЫЕ ЛОГИЧЕСКИЕ ЦЕПИ 1.1 Основные положения алгебры логики Анализ и синтез логических схем осуществляется на базе аппарата алгебры логики или булевой алгебры [14]. Излагать весь аппарат не имеет смысла, так как в инженерной практике используются два-три закона алгебры логики. В алгебре логики переменные могут принимать только два значения, 0 или 1. Для двух аргументов существуют 16 логических функций (операций, логических действий). Над переменными в основном производятся три логических действия: сложение, умножение, отрицание (инверсия), что соответствует функциям ИЛИ, И, НЕ. Все функции в булевой алгебре могут быть описаны с помощью таблицы истинности. В нижеследующих таблицах описаны функции И(f1), ИЛИ(f2),НЕ(f3).
Вместо функции И часто используется термин «конъюнкция», вместо функции ИЛИ - термин «дизъюнкция». По ЕСКД логические элементы, реализующие функции И(f1), ИЛИ(f2), НЕ(f3), изображаются так, как представлено на рисунке.
При написании логических формул для функции И используются следующие знаки : &,, точка или ее отсутствие; для функции ИЛИ - V,+. Функция НЕ обозначается штрихом над аргументом. Мы для обозначения отрицания будем использовать апостроф. Таким образом, можно записать: f1 = x2 & x1 = x2 x1 = x2x1 f2 = x2 V x1 = x2+x1 f3 = x’ Основные законы алгебры Буля. Как уже отмечалось, в булевой алгебре все операции осуществляются с логическими переменными и подчиняются законам алгебры логики.Опишем некоторые из них. а) Переместительный закон а + в = в + а ; ав = ва б) Сочетательный закон ( а + в ) + с = а + ( в + с) ; ( ав )с = а(вс) в) Распределительный закон а( в + с ) = ав + ас ; а + вс = (а + в)( а + с ) г) Закон поглощения а + ав = а( 1 + в ) = а ; а( а + в ) = а + ав = а д) Закон склеивания ав + ав’ = а ; ( а + в )(а + в’) = а е) Идемпотентный закон a + a = a; a & a = a ё) Правила Де Моргана Эти правила справедливы для любого числа аргументов. а + в + с +.... + z = ( а’в’с’...z’ )’ авс... = ( а’ + в’ + с’ +... + z’ )’ Эти правила можно описать таким алгоритмом. Для перехода от логической суммы к логическому произведению необходимо проделать следующие операции : 1) проинвертировать все слагаемые в отдельности; 2) заменить знаки дизъюнкции на знаки конъюнкции; 3) проинвертировать получившееся выражение. Аналогично выполняется переход от логического произведения к логической сумме. В инженерной практике используются лишь правила Де Моргана и закон склеивания(в виде карт Карно). Кроме основных функций И, ИЛИ, НЕ в алгебре логики часто используются функции равнозначности (эквивалентности) и неравнозначности (сумма по модулю 2 ). Для обозначения этих функций используются следующие знаки : равнозначность - ~, сумма по модулю 2 -. Содержание этих функций отражено в таблице.
Из таблицы получаем: f4 = а ~ в = а’в’ + ав f5 = а в = а’в + ав’ Из таблицы видно, что f4 = f5’ или f5 = f4’ Таким образом, а’в’ + ав = ( ав’ + а’в )’, или а ~ в = ( а в )’, а в = (а~в)’ Алгебра множеств. Обычно множества изображаются в виде окружностей, эллипсов, прямоугольников, квадратов и других фигур. Однако переход от двумерности к одномерности, т.е. к скалярным диаграммам, позволяет существенно расширить возможности анализа и синтеза в алгебре множеств. Попробуем доказать идентичность функций и законов в алгебре логики и алгебре множеств. Полная система булевских функций для двух аргументов показана в таблице.
Эти функции для алгебры множеств можно представить с помощью скалярных диаграмм, которые служат основным инструментом алгебры множеств. Здесь и далее в том случае, если аргумент или функция равны нулю, то они изображается тонкой линией, в противном случае – толстой. Все вышеперечисленные законы булевой алгебры легко и просто доказываются с помощью алгебры множеств. Приведем, к примеру, графическое доказательство правила де Моргана для двух аргументов x+y = (x’y’)’. Из скалярных диаграмм видно, что x+y = (x’y’)’. Далее будет показано, что минимизация функций в алгебре множеств не отличается от минимизации логических функций в алгебре логики. Таким образом, мы доказали, что алгебра логики и алгебра множеств идентичны. 1.2 Разновидности логических интегральных схем ( ИС ) Логические ИС, выпускаемые промышленностью, являются функционально полными системами логических элементов и образуют базис построения логических схем. Функционально полная система логических элементов - это такой набор элементов, используя который можно реализовать любую сколь угодно сложную логическую функцию. К числу функционально полных систем относятся, например, системы, реализованные на элементах «И-НЕ» либо на элементах «ИЛИ-НЕ». Наиболее распространены в настоящее время серии 1530,1533,555,533,561,1561, 564,1564,176. Различаются эти серии по быстродействию. Наиболее быстродействующей серией является серия 1530, самой инерционной - серия 176. Задержки в элементах серии 1530 порядка 3 нс, задержки в таких же элементах серии 176 - порядка 200нс. Максимальным потреблением обладает самая быстродействующая серия 1530, минимальным - серия 1564. В состав перечисленных серий входят, например, ИС, представленные на рисунке. На этом рисунке контурными линиями ограничен состав одного корпуса ИС. Пусть необходимо реализовать функцию f = а + вс в базисе И-НЕ. Используя правило Де Моргана, получим: f = ( а’(вс)’)’.Её реализация представлена на рисунке.
1.3. Синтез комбинационных схем Синтез комбинационных схем можно проиллюстрировать решением простой задачи. Задача 1. Приёмная комиссия в составе трех членов комиссии и одного председателя решает судьбу абитуриента большинством голосов. В случае равного распределения голосов большинство определяется той группой, в которой оказался председатель приемной комиссии. Построить автомат, обеспечивающий определение большинства голосов. Решение. Пусть f - функция большинства голосов. f = 1, если большинство членов комиссии проголосовало за приём абитуриента, и f = 0 в противном случае. Обозначим через x4 голос председателя комиссии. x4 = 1, если председатель комиссии проголосовал за приём абитуриента. x3, x2, x1 - голоса членов приёмной комиссии. С учётом вышеуказанных допущений условие задачи можно однозначно представить в виде таблицы истинности. Заполнение таблицы осуществляем с учётом того, что функция f является полностью определённой, т.е. она определена на всех возможных наборах переменных x1 - x4. Для n входных переменных существует N = 2n наборов переменных. В нашем примере N = 24 = 16 наборов. Записывать эти наборы можно в любом порядке, но лучше в порядке возрастания двоичного кода.
Примечание. Здесь и далее под набором будем понимать конъюнкцию всех входных переменных. Существует множество научных определений для набора(конституента,терм,импликанта,минтерм и т.д.),но они только вносят путаницу. Все наборы, на которых функция принимает значение 1, будем называть единичными, или рабочими. Наборы, на которых функция принимает значение 0, будем называть нулевыми, или запрещенными. Для того, чтобы по таблице истинности найти функцию f, достаточно выписать все единичные наборы и соединить их знаком дизъюнкции. Таким образом, f = x4’x3x2x1 + x4x3’x2’x1 + x4x3’x2x1’ + x4x3’x2x1 + x4x3x2’x1’ + x4x3x2’x1 + x4x3x2x1’ + x4x3x2x1 Полученная форма функции называется совершенной дизъюнктивной нормальной формой (СДНФ), так как каждое логическое слагаемое представляет собой конъюнкцию всех аргументов. Очевидно, применяя основные законы булевой алгебры, мы могли бы аналитически уменьшить сложность полученного выражения. Но это наихудший способ минимизации булевых функций. 1.4.Минимизация полностью определённых булевых функций. Существует несколько способов минимизации булевых функций. Прежде всего это метод Квайна-Мак-Класки, метод Блека-Порецкого и метод минимизации с помощью карт Карно или диаграмм Вейча [14]. Здесь будет подробно излагаться метод карт Карно, как самый удобный метод, позволяющий быстро решать задачи минимизации булевых функций от достаточно большого числа аргументов (6-12). При этом получается минимальная форма в базисе И, ИЛИ, НЕ. Карты Карно и диаграммы Вейча хорошо описаны в [9], но лишь для небольшого числа переменных. Существуют карты Карно на 2, 3, 4, 5 и 6 переменных. Причем последние стали использоваться достаточно недавно. На рисунке представлены карты Карно для 2, 3, 4, 5 и 6 аргументов.
Карты и прямоугольники Карно. Метод Карно основан на законе склеивания. Склеиваются наборы, отличающиеся друг от друга значением одного разряда. Такие наборы называются соседними. Карно закодировал клетки своей карты так,что в соседних клетках оказались соседние, а значит, склеивающиеся наборы. Соседними могут быть не только отдельные клетки, которые мы назовем элементарными квадратами Карно, но и целые группы соседних клеток(назовем их прямоугольниками Карно). Под прямоугольником Карно будем понимать некоторую, зачастую разрозненную фигуру покрытия, все соседние клетки которой закодированы соседними наборами. Например, на вышеприведённом рисунке в поле карты для 4-х переменных изображён прямоугольник Карно P, состоящий из четырёх элементарных квадратов Карно, описываемых наборами x4’x3’x2’x1’, x4’x3’x2x1’, x4x3’x2’x1’, x4x3’x2x1’. Если над логической суммой этих четырёх наборов произвести последовательно операции склеивания, то мы аналитически получим результат в виде импликанты (под импликантой будем понимать неполный набор)x3’x1’. Карта Карно позволяет получить этот результат графически значительно быстрее и проще. Для решения этой задачи используем алгоритм графической минимизации.Кстати говоря,сам Карно никакого алгоритма не предложил. Алгоритм графической минимизации логических функций. 1. Заполнить карту Карно нулями и единицами в соответствии с таблицей истинности. 2. Покрыть все единичные наборы минимальным количеством прямоугольников Карно, каждый из которых имеет максимальную площадь. 3. Каждому прямоугольнику Карно соответствует одна импликанта, причём, если в границах прямоугольника Карно какая-либо переменная принимает значения как 0, так и 1, то она склеивается. Примечание. Если в карте Карно нулей окажется меньше чем единиц, то удобнее прямоугольниками Карно покрыть все нулевые наборы. В результате мы получим инверсию минимизируемой функции. Сущность алгоритма достаточно прозрачна. Стремление к минимальному количеству прямоугольников Карно приводит в результате к минимальному количеству слагаемых в булевой функции. Требование получения максимальной площади прямоугольника Карно вызвано стремлением минимизировать длину каждого слагаемого булевой функции. Пусть булева функция Y задана так, что в поле прямоугольников Карно Р и Т вышеприведённого рисунка оказались все единичные наборы, а в остальных клетках карты Карно разместились все нулевые наборы данной функции. В соответствии с пунктом 3 алгоритма Карно прямоугольник Р будет представлен импликантой x3’x1’, а прямоугольник Т - имликантой x2x1. Таким образом, функция Y=x3’x1’ + x2x1. 1.5.Карты Карно для 7, 8, 9 и 10 переменных. До сих пор сохранилось мнение, что карты Карно для 7-10 переменных являются труднообозримыми, поэтому ни в какой литературе,кроме [14], нельзя найти не только описания метода работы с картами Карно на большое количество переменных, но и самих карт. Этим же обстоятельством объясняется тот факт, что до недавнего времени в литературе редко встречались карты Карно даже для 6 переменных. Прежде,чем приступить к рассмотрению многоаргументных карт Карно,покажем на простых примерах, как осуществляется соседнее кодирование для произвольного числа переменных. Для одной переменной существует только соседнее кодирование, так как она кодируется нулём и единицей. Чтобы перейти к соседнему кодированию для двух переменных x2 и x1 предлагается следующая операцию. Напишем в один столбец коды для x1.Между нулём и единицей для столбца x1 проведём ось, которую назовём осью симметрии 1-го ранга. x1 0 ---- 1 Проведём под этим столбцом ось симметрии, которую в дальнейшем будем называть осью симметрии 2-го ранга, и продолжим столбец кодов для x1 симметрично относительно этой оси (симметрично относительно оси симметрии 2-го ранга разместятся и оси симметрии 1-го ранга). x1 0 ---- 1 ------ 1 ---- 0 Дополним одноразрядный код до двухразрядного, для чего выше оси симметрии впишем для x2 нули, а ниже - единицы. x2 x1 0 0 ---- 0 1 ------ 1 1 ---- 1 0 Таким образом, мы осуществили соседнее кодирование для двух переменных. Чтобы построить соседние коды для трёх переменных, проведём под столбцами двухразрядных кодов ось симметрии 3-го ранга и продолжим эти столбцы вниз симметрично относительно оси 3-го ранга, т.е. осуществим симметричное отображение относительно оси 3-го ранга. x2 x1 0 0 ---- 0 1 ------ 1 1 ---- 1 0 --------- 1 0 ---- 1 1 ------ 0 1 ---- 0 0 Дополним двухразрядные коды до трёхразорядных, вписав в третьем разряде нули выше оси Карно 3-го ранга и единицы ниже этой оси. Получим соседнее кодирование для трёх переменных. x3 x2 x1 0 0 0 ---- 0 0 1 ------- 0 1 1 ---- 0 1 0 ------------- 1 1 0 ---- 1 1 1 ------- 1 0 1 ---- 1 0 0 Следовательно, для того, чтобы осуществить соседнее кодирование для (Р+1) переменных, если известно соседнее кодирование для Р переменных, необходимо выполнить следующий алгоритм: 1) под столбцом известного Р-разрядного соседнего кодирования провести ось симметрии (Р+1)-го ранга ; 2) осуществить симметричное отображение относительно оси симметрии (Р+1) - ранга всех Р-разрядных кодов и осей симметрии всех рангов до ранга Р включительно ; 3) дополнить Р-разрядные коды слева одним разрядом, в котором записать 0 для всех кодов выше оси симметрии (Р+1)-го ранга и 1 для кодов, расположенных ниже оси симметрии (Р+1)-го ранга. Соседнее кодирование карт Карно по вышеизложенному алгоритму производится как для вертикальных, так и для горизонтальных сторон карт. Примеры кодирования карт Карно приведены на рисунке. На нём стрелками обозначены оси симметрии, ранг которых отмечен цифрами, стоящими рядом со стрелками.
Карта Карно на 8 переменных. Покрытие всех единичных наборов булевой функции, размещённых в карте Карно, прямоугольниками Карно не вызывает затруднений, если функция зависит не более, чем от 6 переменных. Обозримость карт Карно для большего числа переменных усложняется, так как становится трудно определить, соответствует ли данная фигура покрытия понятию прямоугольника Карно. Определение достоверности прямоугольника Карно основано на принципе симметрии, значительно повышающем обозримость карт Карно, и осуществляется с помощью приводимого ниже алгоритма.
Алгоритм проверки достоверности прямоугольника Карно ( принцип симметрии ) 1. Если предполагаемый прямоугольник Карно (ППК) охватывает одну ось симметрии, либо не охватывает ни одной, то перейти к п.4. 2. Если ППК располагается по обе стороны от нескольких осей симметрии, то он должен быть симметричен относительно той из этих осей, которая имеет максимальный ранг, иначе данная фигура не является прямоугольником Карно. 3. Разбить исходный ППК пополам. Считать любую его половину новым ППК. Перейти к п.1. 4. Конец. Этот алгоритм необходимо применить дважды : относительно горизонтальных и относительно вертикальных осей симметрии. Проверим достоверность прямоугольника Карно А на вышеприведённом рисунке. Прямоугольник А размещается по обе стороны от горизонтальной оси 4-го ранга. Симметричность его очевидна. Верхняя половина фигуры А симметрична относительно горизонтальной оси симметрии 1-го ранга. Так как ППК охватывает одну единственную ось симметрии, то проверка фигуры покрытия А на соответствие принципу симметрии относительно горизонтальных осей закончена. Приступаем к проверке принципа симметрии относительно вертикальных осей симметрии. Фигура покрытия А размещается по обе стороны от вертикальной оси симметрии 4-го ранга и симметрична относительно этой оси. Левая половина фигуры А симметрична относительно оси симметрии 3-го ранга. После повторного деления левая половина фигуры покрытия оказалась симметричной относительно оси симметрии 2-го ранга. После 3-го деления ППК не охватывает ни одной оси симметрии, на этом проверка достоверности прямоугольника Карно заканчивается. Таким образом, фигура покрытия А действительно является прямоугольником Карно. Аналогично доказывается, что фигура покрытия В также является прямоугольником Карно. На рисунке даны примеры фигур, не являющихся прямоугольниками Карно.Фигуры k, m и n не являются прямоугольниками Карно в силу нарушения принципа симметрии. Фигура n не симметрична относительно горизонтальной оси симметрии 2-го ранга, фигура m не симметрична относительно вертикальной оси симметрии 3-го ранга. Фигура k симметрична относительно оси симметрии 3-го ранга, но её половина не симметрична относительно оси 2-го ранга.
Алгоритм «НИИРТА» графической минимизации булевых функций. 1. Заполнить карту Карно нулями и единицами в соответствии с таблицей истинности или заданным алгебраическим выражением. 2. Покрыть все элементарные квадраты Карно, в которых записаны единицы, минимальным количеством фигур покрытия, каждая из которых имеет максимальную площадь. 3. Проверить каждую фигуру покрытия на соответствие принципу симметрии. В противном случае изменить контур фигуры покрытия в соответствии с принципом симметрии так, чтобы она превратилась в прямоугольник Карно. 4. Каждому прямоугольнику Карно соответствует одна импликанта, причём если в границах прямоугольника Карно какая-либо переменная принимает значения как 0, так и 1, то эта переменная не войдёт в импликанту. Применим карту Карно для решения задачи 1. На рисунке даны два варианта решения. f = x4x1 + x4x2 + x4x3 + x3x2x1 f’ = x4’x1’ + x4’x2’ + x4’x3’ + x3’x2’x1’ Эти выражения представляют собой пример дизъюнктивной нормальной формы (ДНФ). В некоторых случаях приведение результата минимизации к скобочной форме позволяет уменьшить количество ИС, необходимые для реализации булевой функции. Скобочная форма для f имеет вид: f = x4(x1 + x2 + x3) + x3x2x1
Карта Карно для решения задачи 1. 1.6.Оценка сложности реализации булевых функций Приблизительную оценку реализации логической функции можно дать по ДНФ, подсчитав коэффициент сложности Кс, равный общему количеству переменных, входящих в ДНФ,плюс количество импликант. Например, для СДНФ к задаче 1 Кс = 32+8=40, а для отминимизированной функции Кс = 9+4=13. При реализации в конкретном элементном базисе обе функции примут вид, представленный на рисунке.Из рисунка видно, что реализация функции по СДНФ потребовала 5 корпусов ИС, по минимальной форме - 1,58 корпуса ИС, по скобочной форме - 1,16 корпуса. Таким образом, минимизация по карте Карно дала нам трёхкратный выигрыш по корпусам ИС относительно реализации по СДНФ. Реализация по скобочной форме уменьшила объём оборудования ещё на 30%. Кстати, ориентировочную оценку аппаратной реализации по коэффициенту сложности можно вычислить по формуле: N = Кс/8, где N – количество корпусов ИС.
Схема автомата до и после минимизации. 1.7. Анализ комбинационных схем. В процессе работы с цифровыми схемами иногда возникает задача определения функции, которую реализует данная структура. Задача 2. На рисунке представлена принципиальная схема комбинационного автомата. Определить его функцию.
Схема автомата к задаче 2. Решение. Определим вначале прмежуточную функцию f1 = x1’’ + x2’’ + x3’’ = x1 + x2 + x3 Затем f2 и f3 f2 = (f1x4)’ = ((x1 + x2 + x3 )x4)’ f3 = (x1x2x3)’ Функция f = f2’ + f3’ = (x1 + x2 + x3)x4 + x1x2x3, т.е. схема реализует скобочную форму автомата, определяющего большинство голосов. 1.8. Формы задания булевых функций. Об одной форме задания булевых функций мы уже говорили - это таблица истинности. Иногда применяется более компактная запись, использующая восьмеричные,десятичные или шестнадцатеричные эквиваленты наборов. Например, набор x4x3x2’x1’ может быть представлен обобщённым кодом 1100, десятичным эквивалентом которого является число 12.Удобнее всего 8-чные и 16-чные коды. Ниже приведена Паскаль-программа синтеза псевдослучайных кодов для задания произвольных булевых функций. program nabor; uses crt; type stroka = string[4]; txt = file of stroka; var f1:txt; x,y,i,j,n,m,b:integer; st:stroka; {-------------------------------------------------------------} function intchar(m:integer):char; var ch:char; begin case m of 0..9: ch:=chr(m+ord('0')); 10..35: ch:=chr(ord('A')+m-10); else begin writeln('Ошибка ввода'); halt; end; end{case}; intchar:=ch; end; {--------------------------------------------------------------} function int10(a:longint;b:integer):string; {Пеpевод целого 10-ичного числа в (2..36)-ичные системы} {a,b - исх. 10-ичн. число и основание сист. счисл. соотв-енно} var s:string; m,i,j:integer; chrarr:array[0..30] of string; begin i:=0; for j:=0 to 30 do chrarr[j]:=' '; repeat m:=(a mod b); chrarr[i]:=intchar(m); a:=a div b; i:=i+1; until (a=0); s:=chrarr[i]; for j:=i-1 downto 0 do s:=s + chrarr[j]; int10:=s; end; {=================================================} begin {$I-} {Внутр.проверка правильности операции с файлом отключена} writeln('**************************************************************'); writeln('* Фоpмиpование файла случайных *'); writeln('* 2-pазpядных 4,8,16-ичных чисел для каpт Каpно *'); writeln('* Pезультиpующий файл - rnd.txt *'); writeln('* Лобанов В.И. 16-09-1997 *'); writeln('**************************************************************'); writeln; write('Введите длину файла n и количество пеpеменных m(4,6,8) '); readln(n,m); assign(f1,'rnd.txt');{Связь f1 с pезультиpующим файлом } {$I+} {Включить внутр.проверку} rewrite(f1); {Открыть файл для записи} case m of 4: begin b:=4; x:=15; end; 6: begin b:=8; x:=63; end; 8: begin b:=16;x:=255; end; end;{case} randomize; for i:=1 to n do begin y:=random(x); st:=int10(y,b); write(st:8); write(f1,st); end; close(f1); writeln; writeln('Файл rnd.txt сфоpмиpован'); writeln('Нажмите клавишу пpобела'); repeat until keypressed; end. Задача 3. Полностью определённая булева функция от 4-х переменных задана десятичными рабочими наборами : РН(4) = 5, 6, 7, 8, 9, 10, 11.Число в скобках указывает количество переменных. Найти минимальную форму этой функции. Решение. Так как функция является полностью определённой, то запрещёнными наборами ЗН(4) являются наборы 0 - 4, 12 - 15. Исходя из этой информации, составляем таблицу истинности и осуществляем минимизацию по карте Карно. Таблица 4.
По карте Карно получаем результат: f = x4x3’ + x4’x3(x1 + x2)
Решение задачи 3. Задание 1. Найти минимальную форму полностью определённых булевых функций, заданных 10-чными рабочим наборами : 1-1) РН(4) = 0, 1, 5, 7 - 9, 13, 15 1-2) РН(5) = 4, 6, 8, 10, 13, 17, 24, 30 1-3) РН(6) = 1 - 8, 16 - 24, 32 - 40 1-4) РН(7) = 7 - 15, 23 - 31, 39 - 47, 50 - 63 1-5) РН(8) = 7 - 15, 100 - 132 1.9. Минимизация недоопределённых булевых функций Функция от n переменных называется недоопределённой, если она задана не на всех 2n наборах. Задача минимизации такой функции заключается в оптимальном доопределении, которое позволило бы покрыть рабочие наборы минимальным количеством прямоугольников Карно, каждый из которых имел бы максимальную площадь. Задача 4. Найти минимальную форму функции y, представленной на рисунке. Решение. Функция задана только на 5 наборах. Добавим к трём рабочим наборам ещё пять, а именно : 0000, 0011, 1000, 1011, 1010. Все оставшиеся наборы доопределим как запрещённые. В результате такого доопределения получим прямоугольник Карно, состоящий из 8 элементарных квадратов Карно. Этому прямоугольнику соответствует функция : y = b’
Решение задачи 4. В этом разделе изложен общепринятый подход к минимизации недоопределённых логических функций(НОЛФ). С точки зрения самодиагностики нужно учитывать входные наборы, на которых функция не определена. Дело в том, что зачастую вышеназванные наборы не должны появляться в нормально работающем устройстве. Поэтому необходимо фиксировать появление таких наборов с целью выработки контрольных сигналов, несущих информацию о сбое или отказе. 1.10. Минимизация системы булевых функций. Существуют достаточно сложные методы минимизации системы булевых функций. Однако все эти методы не дают оптимального решения, поэтому при инженерном синтезе комбинационных схем осуществляется раздельная минимизация функций, которая тоже не всегда обеспечивает минимальное решение, но подкупает простотой. Задача 5. Построить преобразователь двоичного кода, получаемого на выходе делителя частоты на 12, в двоично-десятичный код. Условие задачи отражено в таблице. Делитель работает в коде 8-4-2-1.
Решение. Для каждой функции yi заполняем карту Карно, производим доопределение и осуществляем минимизацию. Весь процесс отражён на рисунке. В результате минимизации получаем систему функций: y1 = x1 y2 = x4’x2 y3 = x3 y4 = x4x2’ y5 = x4x2
Карты Карно к задаче 5. Задача 6. Построить один разряд многоразрядного сумматора. Решение. Пусть ai и вi - значения i-ых разрядов слагаемых а и в, Pi и Si - значения переноса и суммы на выходе i-го разряда, Pi-1 - значение переноса на выходе предыдущего разряда, тогда работу сумматора можно описать с помощью таблицы истинности.
Имеем систему полностью определённых булевых функций. Производим раздельную минимизацию (см. рисунок). Si = ai’вi’Pi-1 + ai’вiPi-1’ + aiвi’Pi-1’ + aiвiPi-1 = Pi-1(ai~вi) + Pi-1’(ai вi) = Pi = вiPi-1 + aiPi-1 + aiвi
Решение задачи 6. Для реализации лучше Pi = aiвi + Pi-1(ai~вi)’, так как может быть использован общий для Si и Pi сомножитель (аi~вi)’. Схема сумматора представлена на рисунке. Здесь же дано условное обозначение одноразрядного сумматора, где А и В - одноразрядные слагаемые, P0 и P1 - входной и выходной переносы, S1 - сумма. На этом же рисунке изображён двухразрядный сумматор, выполненный на микросхеме 133ИМ2. Здесь А1, В1, А2, В2 - соответственно значения первых и вторых разрядов слагаемых А и В; S1 и S2 - 1-ый и 2-ой разряды суммы; P0 - входной перенос для первого разряда, P2’ - выходной перенос.
Схемы сумматоров. Задание 2. 2-1. Построить 2/(2-10) преобразователь для делителя частоты на 24, работающего в коде 16-8-4-2-1. 2-2. Построить 4-входовой сумматор для суммирования одноразрядных двоичных чисел. 2-3. Провести тренировку по применению карт Карно с использованием программы nabor.pas. 1.11. Синтез комбинационных схем на мультиплексорах и ПЛИС. Мультиплексором называется такая комбинационная схема(КС), которая реализует функцию: Y = XiAi, где Xi - i - й входной сигнал, Ai - i - й адресный код. Мультиплексор коммутирует вход Xi на выход Y, если на адресном входе установлен код Ai. Если адресная шина мультиплексора является n - разрядной, то синтез КС по таблице истинности от (n+1) переменных не требует дополнительных элементов. При синтезе автомата для тайного голосования(задача 1 из раздела 1.3) были получены следующие функции адресных входов мультиплексора : A0 = 0; A1 = A2 = A3 = A4 = A5 = A6 = X4; A7 = 1. Удобнее и проще синтезировать КС на базе ПЛИС(программируемых интегральных схем). К их числу относятся программируемые логические матрицы(ПЛМ), программируемая матричная логика(ПМЛ), матрицы логических ячеек(МЛЯ) и перепрограммируемые постоянные запоминающие устройства(ППЗУ).Наиболее популярные ПЛИС: ПЛМ - К556РТ2 ПМЛ - К15556ХП4 МЛЯ - БИС фирм Xilinx, Altera ППЗУ - К155РЕ3,К556РТ4,К573РФ5, К573РФ8. Для ПЛМ, ПМЛ и МЛЯ требуется оязательная минимизация, для ППЗУ необходимо приведение функции к СДНФ. Глава вторая МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ МЕТОДОМ ОБОБЩЁННЫХ КОДОВ В СДНФ функции от n переменных каждый набор xi можно заменить последовательностью нулей и единиц. Такая последовательность носит название обобщённого кода. Метод обобщённых кодов был разработан в конце 60-х годов на 21-й кафедре Академии им. Дзержинского д. т. н. Мавренковым Леонидом Трофимовичем. Дальнейшее развитие метода и доведение его до инженерных методик было выполнено сотрудниками этой кафедры к.т.н. Кустенко А.С., к.т.н. Кузнецовым Н.В. и к.т.н. Салтыковым Ю.А.(см. "Вопросы оборонной техники", 1972 г.). Этот метод до сих пор является самым эффективным методом минимизации логических функций. Например, набору x4x3’x2x1’ соответствует обобщённый код 1010. Для ДНФ обобщённый код (ОК) имеет прочерки на местах отсутствующих переменных. Например, для функции от 5 переменных набору x5x2’ соответствует ОК = 1--0-. Методом обобщённых кодов удобно работать с функциями, заданными таблицами истинности. Причём рабочим наборам соответствуют рабочие обобщённые коды (РОК), запрещённым наборам - запрещённые обобщённые коды (ЗОК). Введём понятие оценочной функции. Оценочная функция F0p(F1p) определяет количество нулей (единиц) для одного разряда всех РОК. Оценочная функция F0з(F1з) определяет количество нулей ( единиц ) для одного разряда всех ЗОК. Функция вида F0 = F0р + F1з называется нулевой оценочной функцией. Функция вида F1 = F1р + F0з называется единичной оценочной функцией. В результате минимизации булевой функции получается минимальная ДНФ (МДНФ), состоящая из простых импликант, т.е. таких импликант, дальнейшая минимизация которых не возможна. В методе обобщённых кодов простой импликанте соответствует минимальный обобщённый код (МОК). Будем говорить, что даннный МОК покрывает определённый РОК, если нули и единицы в этом РОК стоят в тех же разрядах, что и в данном МОК. Сущность метода ОК заключается в том, чтобы по максимуму оценочных функций выбрать такие переменные, которые чаще всего встречаются в РОК и реже всего в ЗОК, и на их основе построить такую совокупность минимальных обобщённых кодов, которая покрывала бы все РОК и не покрывала бы ни одного ЗОК. 2.1. Общий алгоритм определения МОК. Алгоритм 1. 1. Присвоить индексу МОК значение 1, т.е. i :=1. 2. Подсчитать по таблице истинности F0 и F1 для всех разрядов РОК и ЗОК. 3. В качестве базы МОКi (БМОКi) или дополнение к БМОКi выбрать переменную с максимальной F0 или F1. Если F0 = max, то переменная входит в БМОКi нулём. Если F1=max, то переменная входит в БМОКi единицей. Если несколько переменных имеют максимальные оценочные функции, то выбрать в качестве БМОК ту переменную, у которой соответствующая запрещённая оценочная функция (F0з, F1з) имеет минимальное значение; в противном случае в качестве БМОК взять любую переменную с максимальной оценочной функцией. 4. Выписать все РОК и ЗОК, покрываемые базой МОКi. Если БМОКi не покрывает ни одного РОК или покрывает все ЗОК, то приравнять нулю оценочные функции F0 и F1 для данного разряда и перейти к п.3. Если покрываемых ЗОК нет, то перейти к п.6. 5. Подсчитать F0 и F1 для всех разрядов РОК и ЗОК, покрытых данной базой, кроме тех разрядов, которые образуют БМОКi. Присоединить к БМОКi переменную (дополнение к БМОКi ) с максимальной оценочной функцией в соответствии с требованиями п.3. Считать этот ОК новой базой МОКi. Если новая БМОКi покрывает столько же ЗОК, сколько и на предыдущем шаге, то приравнять нулю оценочные функции для дополнения к БМОКi, отбросить присоединённую переменную и добавить к БМОКi переменную с максимальной оценочной функцией в соответствии с требованиями п.3, считать полученный ОК новой БМОКi. Если БМОКi покрывает хотя бы один ЗОК, перейти к п.4. 6. Принять в качестве МОКi базу МОКi. 7. Если все РОК из исходной таблицы истинности покрыты минимальными обобщёнными кодами, перейти к п.9. 8. Выписать из исходной таблицы истинности все ЗОК и те РОК, которые не покрыты минимальными обобщёнными кодами. Считать вновь полученную таблицу исходной таблицей истинности. Увеличить индекс МОК на единицу, т.е. i :=i+1. Перейти к п.2. 9. Конец. Поясним положение пп.4 и 5 алгоритма 1. Пусть таблица истинности состоит из одного РОК 1110 и трёх ЗОК : 1010, 0110 и 1111. 1110 РОК -------------- 1010 0110 ЗОК 1111 --------------- 2232 F0 2212 F1 --------------- После подсчёта оценочных функций оказалось, что для второго разряда F0 = 3 = max. Если в соответствии с максимумом оценочной функции взять в качестве БМОК код --0-, то этот код не покроет ни одного РОК, что недопустимо, т.к. БМОК обязательно должна покрыть хотя бы один РОК. Несколько иная ситуация складывается в том случае, когда БМОК, найденная по максимуму оценочной функции, покрывает часть РОК и все ЗОК. Пусть функция задана пятью РОК и одним ЗОК. 1110 1000 1011 РОК 0111 0010 ------------------- 1010 ЗОК ------------------- 3323 F0 3343 F1 Если в соответствии с максимумом взять в качестве БМОК код --1-, то в конце концов мы построим некоторый ОК, не покрывающий ни одного ЗОК, но длина этого ОК не будет минимальной. Проиллюстрируем выполнение алгоритма 1 примерами. Задача 7. Построить МДНФ булевой функции y, заданной таблицей, по методу ОК.
Решение. 1. Выбираем в качестве БМОК1 переменную x3, т.е. БМОК1 = -1--. Эта БМОК1 покрывает все РОК и один ЗОК. 2. Выписываем эти РОК и ЗОК (см.след. таблицу ). 3. По максимальному F0 = 5 определяем вторую переменную базы МОК1. Это переменная x1. Она входит в БМОК инверсным значением, т.е. БМОК1 = -1-0. 4. Так как БМОК1 = -1-0 не покрывает ни одного ЗОК и покрывает все РОК, то минимизацию считаем законченной и принимаем МОК1 = БМОК1 = -1-0, т.е. y = x3x1’. Такой же результат получается и по карте Карно.
Задача 8. Построить МДНФ функции, заданной таблицей.
Решение. 1. Принимаем БМОК1 по F1 = 10 (можно по F0 =10). БМОК1 = --1----- БМОК1 покрывает один ЗОК и все РОК. 2. Выписываем все РОК и ЗОК, покрываемые БМОК1. После подсчёта оценочных функций оказывается, что максимум F0 приходится на x1, поэтому БМОК1 = --1----0 МОК1 = БМОК1 = --1----0 3.Непокрытым оказался только один РОК. Выписываем этот РОК и все ЗОК в таблицу.
4. Находим БМОК2 = -----1-- МОК2 = БМОК2 = -----1-- Результат минимизации выглядит так : y = x6x1’ + x3 Такой же результат получен и по карте Карно. Задание 3. Найти минимальную форму функций, указанных в задании 1, методом обобщённых кодов.
2.2. Алгоритм соседнего определения базы МОК (алгоритм Мавренкова). Алгоритм 1 требует раздельного размещения РОК и ЗОК. Приведение таблицы истинности к такому виду усложняет метод ОК. Процесс минимизации методом ОК может быть существенно упрощен, если определение БМОК производить с использованием приводимого ниже алгоритма. Алгоритм 2. 1. Присвоить индексу МОК значение 1, т.е. i := 1. 2. Присвоить индексу РОК значение 1, т.е. j := 1. 3. Взять РОК из исходной таблицы истинности и, сравнивая его со всеми ЗОК, определить переменные, по которым РОК может быть склеен с ЗОК. Эта совокупность переменных и будет базой МОКi. Перейти к п.7. 4. Если РОКj не имеет соседних ЗОК, то j := j + 1 и перейти к п.3. Если в таблице истинности нет ни одного РОК, соседнего хотя бы с одним ЗОК, то перейти к п.5. 5. Подсчитать по таблице истинности F0 и F1 для всех разрядов. 6. В качестве базы МОКi (БМОКi ) или дополнения к БМОКi выбрать переменную с максимальной F0 или F1. Если F0 = max, то переменная входит в БМОКi нулём. Если F1 = max, то переменная входит в БМОКi единицей. Если несколько переменных имеют одинаковые оценочные (максимальные) функции, то выбрать в качестве БМОКi ту переменную, у которой соответствующая запрещённая оценочная функция ( F0з или F1з ) имеет минимальное значение, в противном случае в качестве БМОКi взять любую переменную с максимальной оценочной функцией F0 или F1. 7. Выписать РОК и ЗОК, покрываемые базой МОКi. Если БМОКi не покрывает ни одного РОК или покрывает все ЗОК, то приравнять нулю оценочные функции F0 и F1 для данного разряда и перейти к п.6. Если покрываемых ЗОК нет, то перейти к п.9. 8. Подсчитать F0 и F1 для всех разрядов РОК и ЗОК, покрываемых данной базой, кроме разрядов (переменных), образующих БМОКi. Присоединить к БМОКi переменную (дополнение к БМОКi ) с максимальной оценочной функцией в соответствии с требованиями п.6. Считать полученный ОК новой базой МОКi. Если новая БМОКi покрывает столько же ЗОК, сколько и на предыдущем шаге, то приравнять нулю оценочные функции или дополнения к БМОКi, отбросить присоединённую переменную и добавить к БМОКi переменную с максимальной оценочной функцией в соответствии с положениями п.6, считать полученный ОК новой БМОКi.Если БМОКi покрывает хотя бы один ЗОК, перейти к п.7. 9. Принять в качестве МОКi базу МОКi. 10. Если все РОК из исходной таблицы истинности покрыты минимальными обобщёнными кодами, перейти к п.12. 11. Выписать из исходной таблицы истинности все ЗОК и те РОК, которые не покрыты минимальными обобщёнными кодами. Считать вновь полученную таблицу исходной таблицей истинности. Увеличить индекс МОК на единицу, т.е. i := i+1. Перейти к п.2. 12. Конец. Задача 9. Произвести минимизацию булевой функции, заданной таблицей.
Решение. 1. По алгоритму 2 пп. 1-3 для РОК2 находим соседний ЗОК, т.е. находим БМОК1 = ---0----. 2. По алгоритму 2 пп. 7-9 находим МОК1 = ---0--0- Так как МОК1 покрывает все РОК, то в соответствии с п.10 алгоритма 2 получаем y = x5’x2’ Сущность алгоритма 2 заключается в том, что отыскиваются в первую очередь « необходимые « МОК, т.е. МОК для тех РОК, развязывание которых с ЗОК максимально затруднено, так как они развязываются только по тем переменным, по которым возможно склеивание данного РОК со всеми ЗОК. Под развязыванием понимается процесс выявления тех переменных в РОК, которые не встречаются в ЗОК. Задача 10. Произвести минимизацию булевой функции, заданной таблицей.
Решение. 1. По алгоритму 2 пп.1-3 для РОК1 находим БМОК1 = ----0- 2. По алгоритму 2 пп.7, 8 строим таблицу.
3. По алгоритму 2 п.8 из таблицы находим БМОК1 = ---00- 4. По алгоритму 2 п.9 МОК1 = БМОК1 = ---00- 5. По алгоритму 2 для непокрытых РОК (для РОК3) находим БМОК2 = -1----. 6. По алгоритму 2 пп.7, 8, 11 строим таблицу.
7. По алгоритму 2 п.9 находим МОК2 МОК2 = 01---- 8. По алгоритму 2 пп.7, 8, 11 строим следующую таблицу.
9. По алгоритму 2 п.3 находим БМОК3 БМОК3 = ----1- 10. По алгоритму 2 пп. 7, 8, 11 строим таблицу.
11. Из таблицы по алгоритму 2 п.8 находим БМОК3 = ----11 12. По алгоритму 2 пп. 7, 8 строим следующую таблицу.
13. По таблице 17 определяем МОК3 = -1--11 Таким образом, y = x3’x2’ + x5x2x1 + x6’x5 На рисунке представлено решение задачи 10 с помощью карты Карно. Функция y представлена в виде МДНФ. Из рисунка видно, что результаты минимизации по карте Карно и по методу обобщённых кодов совпадают.
Карта Карно к задаче 10. Задача 10а. Произвести минимизацию логической функции, заданной таблицей истинности.
Т.к. РОК3 и ЗОК1 являются соседними по x7,то в качестве БМОК1 выбираем х7’,не обращая внимание на абсолютный максимум F0 для х8.БМОК1 покрывает РОК1 - РОК5 и ЗОК3,ЗОК5.Подсчитаем оценочные функции для выбора дополнения к БМОК1 и получения МОК1.
Дополнение х4’ могло бы привести нас к МДНФ,поэтому мы выберем эквивалентное по оценочной функции дополнение х1,чтобы убедиться в некоторых недостатках метода. В результате получим МОК1 = x7’x1. Поскольку МОК1 покрывает РОК с номерами 1,3 - 5,то стартовая таблица для синтеза БМОК2 выглядит так:
Исходя из этой таблицы получаем БМОК2 = x8’. Для нахождения МОК2 строим следующую таблицу.
Отсюда получаем МОК2 = х8’x5’, который дополнительно покрывает РОК2 и РОК6. Найдём БМОК3.
F0 для х3 имеет максимальное значение,но использовать x3’ в качестве БМОК3 нельзя,поскольку единственный РОК не имеет нуля в данном разряде. Принимаем БМОК3 = x8’. Строим очередную таблицу для синтеза последнего МОК.
< | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
