Главная | О нас | Обратная связь Автоматизация Автостроение Антропология Археология Архитектура Астрономия Предпринимательство Биология Биотехнология Ботаника Бухгалтерский учет Генетика География Геология Государство Демография Деревообработка Журналистика и СМИ Зоология Изобретательство Иностранные языки Информатика Информационные системы Искусство История Кинематография Кораблестроение Кулинария Культура Лексикология Литература Логика Маркетинг Математика Математический анализ Материаловедение Машиностроение Медицина Менеджмент Металлургия Метрология Механика ОБЖ Охрана Труда Педагогика Политология Правоотношение Программирование Производство Промышленность Психология Радио Разное Социология Спорт Статистика Строительство Теология Технологии Туризм Усадьба Физика Физиология Философия Финансы Химия Черчение Экология Экономика Электротехника Минимизация функций по методу Квайна 2020-02-03 164 Обсуждений (0) Минимизация функций по методу Квайна 0.00 из 5.00 0 оценок Скачать документ ⇐ Предыдущая123456 При минимизации по методу Квайна в базисе И, ИЛИ, НЕ исходная ФАЛ задаётся в СДНФ Целью минимизации является нахождение всех первичных импликант и выбор некоторых из них для минимальной записи функции. Импликанта функции - некоторая логическая функция, обращаемая в нуль при наборе переменных, на котором сама функция также равна нулю. Поэтому любой конъюнктивный терм, входящий в состав СДНФ, или группа термов, соединённых знаками дизъюнкции являются импликантами исходной ФАЛ. Импликанты имеют единичные значения только на подмножестве наборов из множества наборов, на которых исходная ФАЛ равна единице. Первичная импликанта функции - импликанта типа элементарной конъюнкции некоторых переменных, никакая часть которой уже не является импликантой.  Задача минимизации по методу Квайна решается путём попарного сравнения всех импликант, входящих в ФАЛ, с целью выявления возможности их неполного склеивания по какой-то переменной на промежуточных этапах. При склеивании снижается ранг термов. Склеивание проводится до тех пор, пока не останется ни одного терма, допускающего склеивание с каким-либо другим термом. Термы, подвергшиеся склеиванию, отмечаются. Неотмеченные термы представляют собой первичные импликанты. После получения множества всех первичных импликант исследуется возможность нахождения простейшей записи ФАЛ. Для этого составляется таблица, в первой строке которой записаны минтермы исходной ФАЛ, а в первом столбце записаны все найденные первичные импликанты. Клетки этой таблицы помечаются в том случае, если первичная импликанта входит в состав какого-либо минтерма исходной ФАЛ. После этого задача упрощения сводится к тому, чтобы найти такое минимальное количество первичных импликант, которые покрывают все столбцы минтермов исходной ФАЛ. Минимизация функций по методу Мак-Класки Недостатком метода Квайна является - необходимость исчерпывающего попарного сравнения или сопоставления всех минтермов на этапе нахождения первичных импликант. С ростом числа минтермов увеличивается количество попарных сравнений. Числовое представление ФАЛ позволяет упростить самый трудоёмкий первый этап. Все минтермы СДНФ ФАЛ записываются в виде их двоичных кодов, а все коды разбиваются по числу единиц на непересекающиеся группы. Минтермы, подлежащие склеиванию, различаются только по одной переменной, а их коды - только в одном разряде. По этой причине сравнению подлежат только двоичные коды минтермов соседних групп. Рассмотрев несколько методов минимизации ФАЛ, можно сделать вывод о том, что для решения нашей задачи наиболее подходящим является метод Мак-Класки.   Минимизируем Y:   Y=010001v010010v010011v010100v010101v010110v010111v011000v011001v110001v110010v110011v110100v110101v110110v110111v111000v111001 i x Q 4 Q 3 Q 2 Q 1 Q 0 Восьмеричное число   2 010001 21   010010 22   010100 24   011000 30   3 010011 23   010101 24   010110 26   011001 31   110001 61   110010 62   110100 64   111000 70   4 010111 27   110011 63   110101 65   110110 66   111001 71   5 110111 67     Склеивание 1 i x Q 4 Q 3 Q 2 Q 1 Q 0 Восьмеричное число   2 0100-1 21, 23   010-01 21, 25   01-001 21, 31   -10001 21, 61   01001- 22, 23   010-10 22, 26   -10010 22, 62   01010- 24, 25   0101-0 24, 26   -10100 24, 64   01100- 30, 31     -11000 30, 70   3 010-11 23, 27   -10011 23, 63   0101-1 25, 27   -10101 25, 65   01011- 26, 27   -010110 26, 66   -11001 31, 71   1100-1 61, 63   110-01 61, 65   11-001 61, 71   11001- 62, 63   110-10 62, 66   11010- 64, 65   1101-0 64, 65   11100- 64, 66   4 -10111 27, 67   110-11 63, 67   1101-1 65, 67   11011- 66, 67     Склеивание 2 i x Q 4 Q 3 Q 2 Q 1 Q 0 Восьмеричное число   2 010--1 21, 23, 25, 27   -100-1 21, 23, 61, 63   -10-01 21, 25, 61, 65   -1-001 21, 31, 61, 71 A 010-1- 22, 23, 26, 27   -1001- 22, 23, 62, 63   -10-10 22, 26, 62, 63   0101-- 24, 25, 26, 27   -1010- 24, 25, 64, 65   -101-0 24, 26, 64, 66   -1100- 30, 70, 31, 71 B 3 -10-11 23, 27, 63, 67   -101-1 25, 27, 65, 67   -1011- 26, 27, 66, 67   110--1 61, 63, 65, 67   110-1- 62, 63, 66, 67   1101-- 64, 65, 66, 67   Склеивание 3 i x Q 4 Q 3 Q 2 Q 1 Q 0 Восьмеричное число

2

-10--1

21, 23, 25, 27, 61, 63, 65, 67

C

-10-1-

22, 23, 26, 27, 62, 63, 66, 67

D

-101--

24, 25, 26, 27, 64, 65, 66, 67

E

21

22

23

24

25

26

27

30

31

61

62

63

64

65

66

67

70

71

A

´

´

´

´

B

Ä

´

Ä

´

C

´

´

´

´

´

´

´

´

D

Ä

´

´

´

Ä

´

´

´

E

Ä

´

´

´

Ä

´

´

´

Y= -1100-v-10-1-v-101--

Минимизируем D ₄

D ₄ = 001001v001010v001011v001100v001101v001110v001111v010100v

v010110v010111v011000v011001v101011v110110

Склеивание 1

Склеивание 2

D ₄ = 0101-0v01100-v-01011v01011-v-10110v001-1-v0011--

Минимизируем D ₃

D ₃ = 000100v000101v000110v000111v001000v001110v010001v010010v

v010011v010110v010111v100011v100101v100111v110001

Склеивание 1

Склеивание 2

D ₃ = 001000v00-110v-10001v100-11v0001--v-001-1v010-1-

Минимизируем D ₂

D ₂ = 000011v000111v001000v001100v001101v001111v010001v010010v

v011000v011001v100000v100001v100010v100101v100111v110001v110110

Склеивание

D₂ = 010010v110110v1000-0v100-00v000-11v-00111

Минимизируем D ₁

D ₁ = 000001v000010v000101v000110v001000v001011v001101v010010v

V100001v100010v100111v101011v110001v110110

Склеивание

D ₁ = 001000v100111v110110v000-10v0-0010v-00010v00-101v1-0001v-01011

Минимизируем D ₀

D ₀ = 000000v000010v000100v000110v001000v001010v001011v001110v

V001111v010010v010011v010111v011001v100000v100010v100101v110110

Склеивание 1

Склеивание 2

D ₀ = 011001v100101v110110v010-11v000--0v00-0-0v-000-0v00--10v001-1-

Заключение

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

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

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

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

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

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

В процессе выполнения работы нами были приобретены практические навыки по курсам « Дискретная математика» и «Цифровые автоматы».

Литература

1. Гудилин А.В. Цифровая схемотехника. Челябинск, 2000.

2. Иванов В.И. Синтез цифровых автоматов для систем связи и управления. Челябинск, 1980

3. Щелкунов Н.Н., Дианов А.П. Процедуры программирования логических матриц, - Микропроцессорные средства и системы, 1986, №2.

4. Иванов В.И. Синтез цифровых автоматов для систем связи и управления, Челябинск, ЧПИ, 1980.

5. Баранов СИ. Синтез микропрограммных автоматов. - Л.: Энергия, 1979.

6. Электронный конспект лекций Гудилин Алексей Евгеньевич.

7. Конспект лекций по курсу цифровые автоматы. ЮУрГУ 2004.

2020-02-03

164

Обсуждений (0)

Минимизация функций по методу Квайна 0.00 из 5.00 0 оценок

Скачать документ