Содержание Введение Метод Квайна-МакКласски Вывод Введение




Скачать 58.72 Kb.
НазваниеСодержание Введение Метод Квайна-МакКласски Вывод Введение
Дата публикации11.05.2013
Размер58.72 Kb.
ТипЗадача
litcey.ru > Информатика > Задача
Содержание

  1. Введение

  2. Метод Квайна-МакКласски

  3. Вывод


1.Введение

Для булевых функций с числом переменных больше 6 целесообразно использовать аналитические или табличные методы минимизации. Следует отметить, что табличные методы более пригодны для реализации в компьютерных программах.

Любой аналитический (табличный) метод минимизации состоит из следующих шагов.

1) Выполняются все неполные склеивания и находятся все простые импликанты.

2) Выполняется задача покрытия всех значений функциинабором простых импликант в результате чего получается множество тупиковых форм функции.

3) Среди множества тупиковых форм выбирается одна, которая по определенным критериям признается минимальной. Чаще всего это критерий минимального количества переменных в аналитическом выражении одной из тупиковых форм функции.
Среди всего множества таких методов можно выделить два направления в решении задач минимизации. Первое состоит в определении всех простых импликант, построении из них тупиковых форм и определении путем перебора минимальной ДНФ. Второе состоит в определении всех существенных импликант, отыскании всех недостающих для реализации заданной функции простых импликант и построении тупиковой ДНФ. Наиболее распространенным среди табличных методов является относящийся к первому направлению метод Квайна-МакКласки.

^ 2.Метод Квайна-МакКласки.
Задача определении множества простых импликант является переборной и разумная организация вычислений может привести к значительному сокращению вычислений. Основной идеей метода Квайна-МакКласки является разбиение множества минимизируемых наборов на группы с равным количеством единиц в каждой. При выполнении склеивания сравниваются только наборы из соседних групп (различающихся на одну единицу). Это приводит к значительному сокращению числа переборов при выполнении склеиваний.
Метод Квайна-МакКласки для кубического представления булевых функций рассмотрим на примере минимизации функции пяти переменных  

T = {0,1,2,3,4,6,8,9,10,11,12,14,17,19,21,22,25,27}.
Рассматриваемый метод состоит из следующих шагов :
1. Упорядочиваются двоичные минтермы (или наборы 0-ранга) в группы в соответствии с числом единиц ( m ), содержащихся с их коде (m - индекс группы).
2. Группы располагаются в порядке возрастания m, начиная с m = 0 (нулевой набор).

3. Чтобы 2 произвольные конституенты 1 порождали при склеивании нек. импликанту – необходимо и достаточно выполнение 3-х условий:

a) |index(X1) – index(X2)| = 1 (т.е было различие только в одном разряде)

b) |XL – XK| = 2M, где M = 0,1,2… (т.е разница между ними должна быть равна 2 в какой-то степени)

c) XL >XK =>index(XL) > index(XK) (т.е для склеивания модуль XL может быть больше модуля XK, только тогда, когда индекс XL больше индекса XK (на 1 – см. п.1))

4. Чтобы производить склеивание импликант произвольного уровня, необходимо и достаточно:

a) равенство последовательности разностей

b) выполнение пункта 3.b, за значения модулей берутся младшие разряды импликант данного уровня.

После выполнения склеивания выполняется поглощение одинаковых кубов ( два и более одинаковых куба заменяются одним ).
5. Если одна импликанта поглощается другими(другой) – она вычеркивается.

Невычеркнутые импликанты представляют собой минимальный набор и являются простыми импликантами и представляют сокращенную ДНФ.


index

Модуль Xi

1-й уровень

2-й уровень

3-й уровень

0

0

(0,1) (1)

(0,2) (2)

(0,4) (4)

(0,8) (8)

(0,1,2,3) (1) (2)

(0,1,8,9) (1) (8)

(0,1,2,3) (2) (1)

(0,2,4,6) (2) (4)

(0,2,8,10) (2) (8)

(0,2,4,6) (4) (2)

(0,4,8,12) (4) (8)

(0,2,8,10) (8) (2)

(0,4,8,12) (8) (4)

(0,1,8,9) (8) (1)



(0,1,2,3,8,9,10,11) (1) (2) (8)

(0,1,2,3,8,9,10,11) (1) (8) (2)

(0,2,4,6,8,10,12,14) (2) (4) (8)

(0,1,2,3,8,9,10,11) (2) (8) (1)

(0,2,4,6,8,10,12,14) (2) (8) (4)

(0,2,4,6,8,10,12,14) (4) (8) (2)



1

1

2

4

8

(1,3) (2)

(1,9) (8)

(1,17) (16)

(2,3) (1)

(2,6) (4)

(2,10) (8)

(4,6) (2)

(4,12) (8)

(8,9) (1)

(8,10) (2)

(8,12) (4)


2

3

6

9

10

12

17

(1,3,9,11) (2) (8)

(1,3,17,19) (2) (16)

(1,3,9,11) (8) (2)

(1,9,17,25) (8) (16)

(1,9,17,25) (16) (8)

(1,3,17,19) (16) (2)

(2,3,10,11) (1) (8)

(2,6,10,14) (4) (8)

(2,3,10,11) (8) (1)

(2,6,10,14) (8) (4)

(4,6,12,14) (2) (8)

(4,6,12,14) (8) (2)

(8,9,10,11) (1) (2)

(8,9,10,11) (2) (1)

(8,10,12,14) (2) (4)

(8,10,12,14) (4) (2)

(8,10,12,14) (4) (2)

(3,11) (8)

(3,19) (16)

(6,14) (8)

(6,22) (16)

(9,11) (2)

(9,25) (16)

(10,11) (1)

(10,14) (4)

(12,14) (2)

(17,19) (2)

(17,21) (4)

(17,25) (8)

(1,3,9,11,17,19,25,27) (2)(8)(16)

(1,3,9,11,17,19,25,27) (2)(16)(8)

(1,3,9,11,17,19,25,27) (8)(2)(16)

3

11

14

19

21

22

25

(3,11,19,27) (8) (16)

(3,11,19,27) (16) (8)

(9,11,25,27) (2) (16)

(9,11,25,27) (16) (2)

(17,19,25,27) (2) (8)

(17,19,25,27) (8) (2)

(11,27) (16)

(19,27) (8)

(25,27) (2)

4

27


рис. 1.1

На рис. 1.1 иллюстрируется описанный ранее метод Квайна-МакКласки.
Синим выделены простые импликанты(а точнее набор элементов, которые эти импликанты однозначно идентифицируют) – т.е. те импликанты, которые невозможно поглатить другими(другой), которые и будут составлять минимальную ДНФ.
Красным зачеркнутым шрифтом отмечены поглощаемые импликанты. Они получаются на каждом шаге и, после обнаружения того, что они являются поглощаемыми, не учавствуют в дальнейшем склеивании.
Таким образом получен минимальный набор

(6,22) (16)

(17,21) (4)

(0,2,4,6,8,10,12,14) (2) (4) (8)

(1,3,9,11,17,19,25,27) (2)(8)(16)
Проанализируем последовательность модулей для каждого набора и определим элементарные конъюнкции

Пример

(6,22)

Модуль/набор

Конъюнкция

6

X5 X4 X3 X2 X1

22

X5 X4 X3 X2 X1

(6,22)

X4 X3 X2 X1


Для всех наборов


Модуль/набор

Конъюнкция

(6,22)

X4 X3 X2 X1

(17,21)

X5 X4 X2 X1

(0,2,4,6,8,10,12,14)

X5 X1

(1,3,9,11,17,19,25,27)

X3 X1


Вид МДНФ для исходной функции
TМДНФ = X4 X3 X2 X1 + X5 X4 X2 X1 + X5 X1 + X3 X1
3.Вывод

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

Похожие:

Содержание Введение Метод Квайна-МакКласски Вывод Введение iconСодержание Введение 3 Кавказская война 4 Заключение 11 Список литературы 12 Введение
Северным Кавказом и Россией существовали и ранее, в последние годы особенно обострился вопрос отношений между ними. По этому поводу...
Содержание Введение Метод Квайна-МакКласски Вывод Введение iconОсновы журналистики содержание
Введение в дисциплину
Содержание Введение Метод Квайна-МакКласски Вывод Введение iconВозрастание роли экономической функции семьи содержание
Введение  3
Содержание Введение Метод Квайна-МакКласски Вывод Введение iconЛитература 56 введение. Проблема групп, в которые объединены люди...
Введение 3
Содержание Введение Метод Квайна-МакКласски Вывод Введение iconПрохоров Е. П. Введение в теорию журналистики: Учебное пособие
Введение в журналистику — один из базовых теоретических курсов, дающих студентам инструментарий для анализа профессиональной деятельности,...
Содержание Введение Метод Квайна-МакКласски Вывод Введение iconСодержание введение
I. психолого-педагогические основы формирования орфографического навыка в начальной школе
Содержание Введение Метод Квайна-МакКласски Вывод Введение iconСодержание введение
«Управление дебиторской и кредиторской задолженностями строительного предприятия и пути их снижения»
Содержание Введение Метод Квайна-МакКласски Вывод Введение iconСодержание введение 3
Анализ ипотечного кредитования на примере мещанского отделения сберегательного банка РФ №7811 6
Содержание Введение Метод Квайна-МакКласски Вывод Введение iconСодержание введение 4
Организация англией крестового похода на СССР (становление англо–германского союза) 10
Содержание Введение Метод Квайна-МакКласски Вывод Введение iconСодержание 2 введение 3
Теоретические основы финансового планирования как фактора оптимизации финансовой деятельности 4
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
litcey.ru
Главная страница