Факторизация и декомпозиция булевой функции

Факторизация МДНФ заключается в выносе общих переменных за скобки, что может привести к уменьшению цены схемы, но увеличиванию задержки.

(1) f = _{1 2}X_{3 4} ˅ ₁X_{2 3 4} ˅ X_{1 2}X₃X₄ ˅ X₁X_{2 3}X₄ ˅ ₃X₅ ˅ X₂X₅ ˅ X₁X₅ S_Q = 29 (сложена каждая переменная (22) плюс все термы (7))

Вынесем X₁ из (1):

f = X₁ [ ₂X₃X₄ v X_{2 3}X₄ v X₅] v _{1 2}X_{3 4} v ₁X_{2 3 4} v ₃X₅ v X₂X₅

m – сколько вынесли букв 

k – из скольки термов

p – число термов с одной буквой после вынесения

дельта – 1, если вынос из всех термов, 2, если не из всех

S_Q = 28

Дальнейший вынос ₃ не изменит цену, будет также 28.

Вынесем X₅ из (1):

(2) f = _{1 2}X_{3 4} ˅ ₁X_{2 3 4} ˅ X_{1 2}X₃X₄ ˅ X₁X_{2 3}X₄ ˅ X₅ [ ₃ ˅ X₂ ˅ X₁]

S_Q = 26

Решим задачу декомпозиции к факторизованному МДНФ (2). Для это введем вспомогательную функцию ϕ. Такую вспомогательную функцию имеет смысл вводить. только если можно вынести несколько переменных, что в нашем случае невозможно. Декомпозицию осуществить не можем.

 

Попробуем провести факторизацию для МДНФ полученной с помощью карт Карно.

(3) f = X₁X₅ v X₂X₅ v ₃X₅ v ₄ X₅ v X₁X_{2 3}X₄ v X_{1 2}X₃X₄ v ₁X_{2 3 4} v _{1 2}X_{3 4}  S_Q = 32

Вынесем X₅ из (3):

X₅ [X₁ v X₂ v ₃ v ₄ ] v X₁X_{2 3}X₄ v X_{1 2}X₃X₄ v ₁X_{2 3 4} v _{1 2}X_{3 4}

дельта S = 1(4-1)+4-2=5, S_Q = 27

 

ПОСТРОЕНИЕ КОМБИНАЦИОННЫХ СХЕМ

КОМБИНАЦИОННАЯ СХЕМА (НЕФАКТОРИЗОВАННОЙ МДНФ)

Нефакторизованная МДНФ, полученная методом К-М-К (Рисунок 1):

f = _{1 2}X_{3 4} ˅ ₁X_{2 3 4} ˅ X_{1 2}X₃X₄ ˅ X₁X_{2 3}X₄ ˅ ₃X₅ ˅ X₂X₅ ˅ X₁X₅

Рисунок 1 Комбинационная схема МДНФ по методу К-М-К

Задержка: Т = 6τ. Цена схемы по Квайну: S_Q = 21*2+4 = 46

КОМБИНАЦИОННАЯ СХЕМА (КАРТЫ КАРНО)

Факторизованная МДНФ, полученная методом карт Карно (Рисунок 2 Факторизованная комбинационная схема МДНФ по методу карт КарноРисунок 2):

f = X₅ [X₁ v X₂ v ₃ v ₄ ] v X₁X_{2 3}X₄ v X_{1 2}X₃X₄ v ₁X_{2 3 4} v _{1 2}X_{3 4}

Рисунок 2 Факторизованная комбинационная схема МДНФ по методу карт Карно

Задержка: Т = 6τ. Цена схемы по Квайну: S_Q = 20*2+4 =44

КОМБИНАЦИОННАЯ СХЕМА (ФАКТОРИЗОВАННОЙ МДНФ)

Факторизованная МДНФ, полученная методом К-М-К ():

f = _{1 2}X_{3 4} ˅ ₁X_{2 3 4} ˅ X_{1 2}X₃X₄ ˅ X₁X_{2 3}X₄ ˅ X₅ [ ₃ ˅ X₂ ˅ X₁]

Рисунок 3 Факторизованная комбинационная схема МДНФ по методу К-М-К

Задержка: Т = 6τ. Цена схемы по Квайну: S_Q = 19*2+4 =42

КОМБИНАЦИОННАЯ СХЕМА (В БАЗИСЕ ЖЕГАЛКИНА)

Для начала преобразуем КДНФ с помощью треугольника Паскаля в базис Жегалкина. Составим два треугольника, один с d равным 0 (Рисунок 4), второй с d равным 1 (

Рисунок 5).

Рисунок 4 Треугольник Паскаля, d = 0

f = x₂ ⊕ x₃ ⊕ x₁x₂ ⊕ x₁x₃ ⊕ x₂x₄ ⊕ x₃x₄ ⊕ x₄x₅ ⊕ x₁x₂x₅ ⊕ x₁x₃x₅ ⊕ x₁x₄x₅ ⊕ x₂x₄x₅ ⊕ x₃x₄x₅

S_Q = 27 + 12 = 39

Рисунок 5 Треугольник Паскаля, d = 1

f = x₂ ⊕ x₃ ⊕ x₅ ⊕ x₁x₂ ⊕ x₁x₃ ⊕ x₂x₄ ⊕ x₂x₅ ⊕ x₃x₄ ⊕ x₃x₅ ⊕ x₁x₂x₅ ⊕ x₁x₃x₅ ⊕ x₂x₄x₅ ⊕ x₁x₃x₄x₅ ⊕ x₂x₃x₄x₅ ⊕ x₁x₂x₃x₄x₅

S_Q = 37 + 15 = 52

Первый полином Жегалкина имеет меньшую цену из двух, поэтому его мы отобразим на комбинационной схеме (Рисунок 6).

 

X₅⊕X₃⊕X₃X₅⊕X₃X₄⊕X₂⊕X₂X₅⊕X₂X₄⊕X₂X₄X₅⊕X₂X₃X₄X₅⊕X₁X₃⊕X₁X₃X₅⊕X₁X₃X₄X₅⊕X₁X₂⊕X₁X₂X₅⊕X₁X₂X₃X₄X₅

Рисунок 6 Комбинационная схема в базисе Жегалкина

Задержка: Т = 6τ. Цена схемы по Квайну: S_Q = 52 (цена больше, чем по формуле из-за ограничений на входы)

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ

 логический элемент (лэ) или

 

 лэ и

 

 лэ инвертор

 лэ модуль 2

Знак дизъюнкции – v;

Знак конъюнкции опускается;

Знак отрицания – надчеркивание ();

Знак сложения по модулю 2 – ⊕;

При склейке 1 и 0 превращаются в -

Пересечения вершин и импликант отмечены знаком *, элементы ядра - х;

Вычеркнутые строки и столбцы выделены оранжевым цветом.

 

ЗАКЛЮЧЕНИЕ

В данной работе булево выражение 2 < |(X₂X₁0)₁₀ - (X₃X₄X₅)₁₀| <= 5 с неопределенными термами заданными функцией |(X₂X₁0)₁₀ - (X₃X₄X₅)₁₀| = 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