История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Топ:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Определение места расположения распределительного центра: Фирма реализует продукцию на рынках сбыта и имеет постоянных поставщиков в разных регионах. Увеличение объема продаж...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Дисциплины:
2017-09-26 | 1174 |
5.00
из
|
Заказать работу |
|
|
Это наиболее удобный метод минимизации булевых функций при небольшом числе переменных.
Карта Вейча для двух переменных (а), для трех (б), для четырех (в), для пяти (г), представляет собой таблицу с определенным порядком следования наборов (в клетках таблицы – номера минтермов соответствующего числа переменных) (рис.1.3).
Рис.1.3.
Для удобства пользования картами на полях проставляют значения переменных.
Таблица функции записывается в карту обычным способом 1(0) – в квадратах, соответствующих наборам, где f(x1 x2 … xn)=1(0).
Следует иметь виду, что порядок расположения наборов таков, что при переходе между соседними квадратами по строке или столбцу меняется форма лишь одной переменной в наборе. В этом смысле первая строка карты является соседней с последней, а первый столбец – соседний с последним.
Отсюда возникают возможности проведения операции склеивания, исходя из расположения единиц в карте Вейча.
Правила склеивания с помощью карт Вейча.
Два минтерма склеиваются (рис.1.4), если они расположены:
1) по соседству – в одной строке или одном столбце (рис.1.4,а);
2) в противоположных концах одной строки или одного столбца (рис.1.4,б);
3) в одинаковых местах двух карт (рис.1.4,в), последнее – для n>4.
рис.1.4.
Алгоритм метода минимизации с помощью карт Вейча.
1) Нанести функцию на карту.
2) Каждый квадрат, содержащий «1», проанализировать с точки зрения «склеивания» с другими во всех возможных комбинациях.
3) Выбираются те комбинации, которые объединяют наибольшее количество единиц и при этом накрывают все единицы карты функции. Они являются простыми импликантами функции.
4) Если только одна импликанта покрывает какую-либо единицу на карте, то эта импликанта является существенной (обязательной).
|
5) Из совокупности простых импликант выбираются минимальные формы функции.
Метод позволяет получить все возможные МДНФ:
Метод Блека-Порецкого.
Используется для получения сокращенной ДНФ из любой произвольной функции представления [5].
Идея построения сокращенной ДНФ по произвольной ДНФ вытекает из следующего определения: если в ДНФ для данной функции f(x1 … xn) входит две конъюнкции вида Axi и Bxi, то имеет место равенство D=D\/AB, где D – ДНФ, эквивалентная функция f.
Алгоритм метода Блека-Порецкого.
1. Провести все возможные склеивания любых двух смежных термов, представляющих соответствующие элементарные конъюнкции, получить L-разрядный троичный набор и построить матрицу ранга n.
2. Над полученными элементарными конъюнкциями ранга (n-1) провести операции склеивания и поглощения, образовать элементарные конъюнкции нижнего ранга и т.д.
3. Процесс закончить, когда после операции склеивания и поглощения окажется, что в ДНФ отсутствуют члены, дальнейшее поглощение которых невозможно, т.е. когда будет получена сокращенная ДНФ.
4. Строится импликантная матрица и определяется максимальное покрытие.
Метод удобен при машинных способах минимизации.
Пример. Найти минимальную форму для заданной функции:
1. Матрица исходных данных 3. Матрица ранга (n-2)
0 0 0 1 2 0 2 1
0 0 1 0 2 0 2 1
0 0 1 1 2 0 1 2
1 0 0 1 2 0 1 2
1 0 1 0
1 0 1 1
2. Матрица ранга (n-1)*
0 0 2 1
2 0 0 1
0 0 1 2
2 0 1 0
2 0 1 1
1 0 2 1
1 0 1 2
4. Вычеркиваем одинаковые строки матрицы ранга (n-2) и получаем
A B C D
2 0 2 1
2 0 1 2
5.
где 0 – инверсия переменной, 1 – переменная, 2 – отсутствует переменная.
|
|
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!