Mots (708404), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Любую функцию от n переменных можно представить в виде (см.(2.2))

(2.2)

означает, что коллективные члены формируются только для таких наборов (α₁, α₂,…, α_n) для которых функция принимает единичное значение.

Форма (2.2) определяет алгоритм перехода от таблицы истинности к аналитическому ее виду. Для такого перехода используется следующий алгоритм:

а) Выбрать в таблице истинности все наборы, в которых функция обращается в единицу.

б) Выписать конъюнкции, соответствующие этим наборам аргументов. При этом если аргумент х_i входит в данный набор как «1», то он вписывается без изменения в конъюнкцию, соответствующую данному набору. Если же входит в данный набор как «0», то в соответствующую конъюнкцию вписывается его отрицание.

в) Все полученные конъюнкции объединяют знаком дизъюнкции.

Для функции у₃ СДНФ будет иметь вид:

2.2.2 Конъюнктивная совершенная нормальная форма

Любую функцию от n переменных можно представить в виду:

f=

означает, что коллективные члены формируются только для таких наборов, (α₁, α₂, …, α_n) для которых функция принимает нулевое значение.

Следующий алгоритм позволяет перейти от табличной записи функции к СКНФ:

а) Выбрать в таблице истинности все наборы, в которых функция обращается в «0».

б) Выписать дизъюнкции, соответствующие этим наборам аргументов. При этом если аргумент х_i входит в данный набор как «0», то он вписывается без изменения в дизъюнкцию, соответствующую данному набору. Если же входит в данный набор как «1», то в соответствующую дизъюнкцию вписывается его отрицание.

в) Все полученные дизъюнкции объединяют знаком конъюнкции

Функция У₃ в виде СКНФ будет иметь вид:

2.3 Минимизация булевых функций

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

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

1. метод неопределенных коэффициентов

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

3. карты Карно

Для примера в курсовом проекте рассмотрена минимизация этими способами для функции y₃.

2.3.1 Пример минимизации методом неопределенных коэффициентов

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

Если теперь задавать всевозможные наборы значений аргументов и приравнивать полученное после этого выражение значению функции на выбранных наборах, то получим систему 2⁴ уравнений для определения коэффициентов К:

Находим выражения, имеющие в правой части ноль. Исходя из определения дизъюнкции вычеркиваются все элементы в этих уравнениях и эти же элементы находящиеся в других уравнениях. В итоге получим уравнения:

Из оставшихся коэффициентов приравниваем единице коэффициент, определяющий конъюнкцию наименьшего возможного ранга, а остальные коэффициенты в левой части данного уравнения приравняем нулю(это можно сделать, так как дизъюнкция обращается а единицу, если хотя бы один член ее равен единице). Тогда уравнения примут вид:

2.3.2 Пример минимизации методом Квайна-Мак-Класки.

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

Метод Квайна состоит из последовательного выполнения этапов:

1. Нахождение первичных импликант

2. Расстановка меток

3. Нахождение существенных импликант

4. Вычеркивание лишних столбцов

5. Вычеркивание лишних

6. Получение минимального покрытия

Выполним, приведенные этапы, для функции У₃.

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

СДНФ, которую мы нашли ранее, для функции У₃ имеет вид:

Составим минитермы для этой функции:

Таблица 2.2.1

Расстановка меток. Остальные этапы нужны, чтобы отбросить некоторые первичные импликанты. На данном этапе составляется таблица, число строк которой равно числу полученных первичных импликант, число столбцов совпадает с числом минитермов СДНФ. Если в некоторый минитерм СДНФ входит какая – либо из первичных импликант, то на пересечении соответствующего столбца и строки ставится метка. В таблице 2.2.2 приведем результат расстановки меток:

Таблица 2.2.2

Нахождение существенных импликант. Если в каком – либо из столбцов таблицы меток стоит только одна метка, то первичная импликанта, стоящая в соответствующей строке, называется существенной импликантой. Все существенные импликанты запоминаются. А из таблицы меток исключаются строки, соответствующие существенным импликантам, и столбцы минитермов «покрываемых» этими существенными импликантами.

Существенными являются импликанты 0-00 и -011. Поэтому вычеркиваем 1-ю и 3-ю строки и столбцы: 1, 5, 2, 7.

Составим сокращенную таблицу меток:

Таблица 2.2.3

Выбор минимального покрытия. Исследуется результирующая таблица. Выбирается такая совокупность первичных импликант, которая иссключает метки во всех столбцах (по крайней мере по одной в каждом столбце). При нескольких возможных вариантах такого выбора отдается предпочтение варианту покрытия с минимальным суммарным числом букв в простых импликантах, образующих покрытие.

С учетом существенных импликант получим две МДНФ для этой функции имеет вид:

1.

2.

Число букв составляющих простые импликации в каждом варианте одинаково. Во втором варианте на одно отрицание меньше, поэтому берем его за искомое:

2.3.3 Пример минимизации картами Карно

Данный метод для минимизации функции в коде Грея. В каждую ячейку записывается значение функции на данном наборе. Затем выделяются группы ячеек размером 2^a*2^b , где a, bε[0,1,2…], в которых функция принимает значение «1». В каждую группу должно входить максимальное число ячеек. Таких групп должно быть минимальное количество. Каждой группе будет соответствовать конъюнктивный член размером n-a-b. Для получения МДНФ каждую группу надо просматривать в горизонтальном и вертикальном измерениях, с нахождения таких переменных, которые не меняют своего значения в пределах группы. Если переменная не меняет своего нулевого значения, то она вписывается в конъюнкцию с отрицанием, если не меняет своего единичного значения, то вписывается без отрицания. Если имеются разорванные группы, то карту Карно надо свернуть в цилиндр. На неопределенных наборах следует доопределить нулем или единицей, в соответствии с выбираемой группой ячеек. Каждая единичная ячейка должна быть включена хотя бы в одну группу.

Составим карту Карно для функции У₃ (рисунок 2.3.1).

	x3x4
x1x2		00	01	11	10
	00	1		1
	01	1
	11	1			1
	10			1	1

Рис. 2.3.1 Карта Карно для функции У₃

Таким образом, для функции У₃ в МДНФ будет иметь следующий вид:

Характеристики

Список файлов реферата