Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Факторизация и декомпозиция булевой функции ⇐ ПредыдущаяСтр 4 из 4
Факторизация МДНФ заключается в выносе общих переменных за скобки, что может привести к уменьшению цены схемы, но увеличиванию задержки. (1) f = 1 2X3 4 ˅ 1X2 3 4 ˅ X1 2X3X4 ˅ X1X2 3X4 ˅ 3X5 ˅ X2X5 ˅ X1X5 SQ = 29 (сложена каждая переменная (22) плюс все термы (7)) Вынесем X1 из (1): f = X1 [ 2X3X4 v X2 3X4 v X5] v 1 2X3 4 v 1X2 3 4 v 3X5 v X2X5 m – сколько вынесли букв k – из скольки термов p – число термов с одной буквой после вынесения дельта – 1, если вынос из всех термов, 2, если не из всех SQ = 28 Дальнейший вынос 3 не изменит цену, будет также 28. Вынесем X5 из (1): (2) f = 1 2X3 4 ˅ 1X2 3 4 ˅ X1 2X3X4 ˅ X1X2 3X4 ˅ X5 [ 3 ˅ X2 ˅ X1] SQ = 26 Решим задачу декомпозиции к факторизованному МДНФ (2). Для это введем вспомогательную функцию ϕ. Такую вспомогательную функцию имеет смысл вводить. только если можно вынести несколько переменных, что в нашем случае невозможно. Декомпозицию осуществить не можем.
Попробуем провести факторизацию для МДНФ полученной с помощью карт Карно. (3) f = X1X5 v X2X5 v 3X5 v 4 X5 v X1X2 3X4 v X1 2X3X4 v 1X2 3 4 v 1 2X3 4 SQ = 32 Вынесем X5 из (3): X5 [X1 v X2 v 3 v 4 ] v X1X2 3X4 v X1 2X3X4 v 1X2 3 4 v 1 2X3 4 дельта S = 1(4-1)+4-2=5, SQ = 27
ПОСТРОЕНИЕ КОМБИНАЦИОННЫХ СХЕМ КОМБИНАЦИОННАЯ СХЕМА (НЕФАКТОРИЗОВАННОЙ МДНФ) Нефакторизованная МДНФ, полученная методом К-М-К (Рисунок 1): f = 1 2X3 4 ˅ 1X2 3 4 ˅ X1 2X3X4 ˅ X1X2 3X4 ˅ 3X5 ˅ X2X5 ˅ X1X5 Рисунок 1 Комбинационная схема МДНФ по методу К-М-К Задержка: Т = 6τ. Цена схемы по Квайну: SQ = 21*2+4 = 46 КОМБИНАЦИОННАЯ СХЕМА (КАРТЫ КАРНО) Факторизованная МДНФ, полученная методом карт Карно (Рисунок 2 Факторизованная комбинационная схема МДНФ по методу карт КарноРисунок 2): f = X5 [X1 v X2 v 3 v 4 ] v X1X2 3X4 v X1 2X3X4 v 1X2 3 4 v 1 2X3 4
Рисунок 2 Факторизованная комбинационная схема МДНФ по методу карт Карно Задержка: Т = 6τ. Цена схемы по Квайну: SQ = 20*2+4 =44 КОМБИНАЦИОННАЯ СХЕМА (ФАКТОРИЗОВАННОЙ МДНФ) Факторизованная МДНФ, полученная методом К-М-К (): f = 1 2X3 4 ˅ 1X2 3 4 ˅ X1 2X3X4 ˅ X1X2 3X4 ˅ X5 [ 3 ˅ X2 ˅ X1] Рисунок 3 Факторизованная комбинационная схема МДНФ по методу К-М-К Задержка: Т = 6τ. Цена схемы по Квайну: SQ = 19*2+4 =42 КОМБИНАЦИОННАЯ СХЕМА (В БАЗИСЕ ЖЕГАЛКИНА) Для начала преобразуем КДНФ с помощью треугольника Паскаля в базис Жегалкина. Составим два треугольника, один с d равным 0 (Рисунок 4), второй с d равным 1 (
Рисунок 5). Рисунок 4 Треугольник Паскаля, d = 0 f = x2 ⊕ x3 ⊕ x1x2 ⊕ x1x3 ⊕ x2x4 ⊕ x3x4 ⊕ x4x5 ⊕ x1x2x5 ⊕ x1x3x5 ⊕ x1x4x5 ⊕ x2x4x5 ⊕ x3x4x5 SQ = 27 + 12 = 39 Рисунок 5 Треугольник Паскаля, d = 1 f = x2 ⊕ x3 ⊕ x5 ⊕ x1x2 ⊕ x1x3 ⊕ x2x4 ⊕ x2x5 ⊕ x3x4 ⊕ x3x5 ⊕ x1x2x5 ⊕ x1x3x5 ⊕ x2x4x5 ⊕ x1x3x4x5 ⊕ x2x3x4x5 ⊕ x1x2x3x4x5 SQ = 37 + 15 = 52 Первый полином Жегалкина имеет меньшую цену из двух, поэтому его мы отобразим на комбинационной схеме (Рисунок 6).
X5⊕X3⊕X3X5⊕X3X4⊕X2⊕X2X5⊕X2X4⊕X2X4X5⊕X2X3X4X5⊕X1X3⊕X1X3X5⊕X1X3X4X5⊕X1X2⊕X1X2X5⊕X1X2X3X4X5 Рисунок 6 Комбинационная схема в базисе Жегалкина Задержка: Т = 6τ. Цена схемы по Квайну: SQ = 52 (цена больше, чем по формуле из-за ограничений на входы) УСЛОВНЫЕ ОБОЗНАЧЕНИЯ логический элемент (лэ) или
лэ и
лэ инвертор лэ модуль 2 Знак дизъюнкции – v; Знак конъюнкции опускается; Знак отрицания – надчеркивание (); Знак сложения по модулю 2 – ⊕; При склейке 1 и 0 превращаются в - Пересечения вершин и импликант отмечены знаком *, элементы ядра - х; Вычеркнутые строки и столбцы выделены оранжевым цветом.
ЗАКЛЮЧЕНИЕ В данной работе булево выражение 2 < |(X2X10)10 - (X3X4X5)10| <= 5 с неопределенными термами заданными функцией |(X2X10)10 - (X3X4X5)10| = 1 было рассмотрено в двух базисах: логическом (3 операции) и Жегалкина (2 операции). При интегральной технологии с точки зрения надежности и стоимости использование однотипных элементов весьма предпочтительно. На мой взгляд было бы интересно изучить функцию в других базисах, например «И-НЕ» (функция Шеффера) и «ИЛИ-HE» (функция Пирса), чтобы сравнить насколько они эффективней полинома Жегалкина. В перспективе было бы интересно поменять основной критерий эффективности с цены по Квайну на задержку сигнала. Данная курсовая работа может представлять интерес для людей тесно связанных с комбинационными схемами и их проектированием. В процессе написания курсовой работы я научился минимизации булевых функций с помощью метода К-М-К, метода Петрика и карт Карно. Определив наиболее минимальную форму, были построены четыре схемы: МДНФ по методу К-М-К, она же после факторизации, факторизованная МДНФ полученная по методу карт Карно, а также МДНФ в базисе Жегалкина. Наиболее трудоемким оказался метод К-М-К, потому что он требует длительной концентрации внимания при склеивании кубов. В данной работе было произведено 32+18*2+12 = 80 склеек. От результата этого метода зависят две комбинационные схемы и факторизация с декомпозицией, поэтому ошибка на начальных этапах может дорого стоить.
Результаты курсовой работы заставили меня обратить внимание на следующие пункты: - факторизация может улучшить цену, не меняя задержку. В моем случае так и вышло. Задержка не изменилась, цена снизилась. - декомпозиция не всегда возможна для улучшения характеристик схемы. Я не нашел способа эффективной замены на новую функцию. - сложность минимизации различна при использовании разных методов. Метод К-М-К прост по своей сути, но требует хорошей концентрации, чтобы не допустить ошибок. Метод карт Карно требует развитое воображение, чтобы увидеть какие зоны самые большие и как их можно объединить. - цена минимальной функции была различна для разных методов, самая низкая была найдена при использовании метода К-М-К и дальнейшей факторизации. Благодаря нескольким итерациям исправления ошибок, используемые методы прочно закрепились в моей памяти. СПИСОК ЛИТЕРАТУРЫ 1. Рябова О. Н. Математическая логика. Курсовая работа: методические указания к выполнению курсовой работы для студентов направления бакалавриата / О. Н. Рябова – СПб: СПбГУПТД 2019. – 34 с. 2. Тѐрушкина, О. Б. Математическая логика. Курсовая работа: методические указания к выполнению курсовой работы для студентов подготовки бакалавриата / О. Б. Тѐрушкина – СПб: СПбГУПТД, 2017. – 15 с. 3. Редактор схемы логических элементов Режим доступа: https://www.semestr.online/graph/logic-gate.php. (Дата: 19.06.2020) 4. Онлайн-калькулятор для метода Петрика Режим доступа: https://www.kontrolnaya-rabota.ru/s/mathlogic/. (Дата: 19.06.2020) 5. Довгий П. С. Синтез комбинационных схем: учебно-метод.пособие к курсовой работе по дисциплине «Дискретная математика» / П. С. Довгий, В. И. Поляков. – СПб: СПбГУ ИТМО, 2009. – 64 с. 6. Новиков Ф.А. Дискретная математика для программистов: учебник для вузов. 2-е изд.- Питер, 2006.- 368 с. 7. ГОСТ 7.32-2001, ГОСТ 7.0.3-2006, ГОСТ 7.1-2003
|
||||||
Последнее изменение этой страницы: 2021-05-27; просмотров: 314; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.117.196.217 (0.036 с.) |