История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Топ:
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Интересное:
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Дисциплины:
2017-09-26 | 1194 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!