рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Геометрическое представление булевых функций

Геометрическое представление булевых функций - раздел Транспорт, Теория цифровых автоматов   В Геометрическом Представлении Фал Значения Входных Переменны...

 

В геометрическом представлении ФАЛ значения входных переменных n - местного набора интерпретируются как координаты в n - мерной декартовой системе координат. Координатная система, в которой располагается геометрическая модель ФАЛ, является n - мерным кубом с единичными рёбрами. Кодам наборов входных переменных соответствуют вершины n - мерного куба. Значения кодов входных наборов переменных, на которых заданная ФАЛ равна единице (при использовании СДНФ для представления ФАЛ) помечаются нечисловыми символами и такой n - мерный куб с помеченными некоторыми вершинами и является геометрической моделью заданной ФАЛ. На рис.6 представлен пример геометрической модели функции двух переменных

Рис.6. Геометрическая модель функции двух переменных

 

На рис.7 представлена геометрическая модель ФАЛ трёх переменных

(23)

Рис.7. Геометрическая модель функции трёх переменных

 

На рис.7а) изображена модель функции трёх переменных в трёхмерном пространстве, а на рис.7б) - в двумерном пространстве на развёртке единичного куба на плоскость. Отметим чрезвычайно важное для практики свойство геометрической модели ФАЛ, на которой видно, что наборы переменных, отличающиеся по одной переменной принадлежат одному ребру единичного куба. Такие наборы переменных называются соседними. На развёртке соседними являются наборы, расположенные на противоположных краях.

Сопоставляя геометрические модели ФАЛ двух переменных и ФАЛ трёх переменных, сформулируем правило построения развёрток на плоскость n - мерных единичных кубов (карт Карно) по имеющимся развёрткам n-1 - мерных единичных кубов (карт Карно меньшей размерности).

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

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

В картах наборы переменных, на которых функция принимает единичные значения, помечаются нечисловыми символами. Карта с нанесёнными на ней значениями ФАЛ называется диаграммой.

Карты, на которых коды наборов изображаются в восьмеричной системе счисления, называются картами Вейча.

На рис.8 приведены примеры построения карт Карно и Вейча для четырёх- и пятиместных наборов переменных. На картах Вейча на рис.8б) и рис.8в) дана аналитическая разметка, указывающая области нулевых значений переменных в наборах. На картах в соседних клетках размещены коды наборов переменных, являющихся соседними, т.е. отличающимися по какой-то одной переменной знаком инверсии. На рис.9 приведена геометрическая модель частично определённой ФАЛ пяти переменных в виде диаграммы Вейча. Те восьмиричные коды наборов переменных, на которых ФАЛ имеет единичное значение, отмечены кружком. Те восьмиричные коды наборов переменных, на которых ФАЛ не определена отмечены круглыми скобками. В большинстве технических применений функции алгебры логики являются частично определёнными, так как не существует технической возможности появления некоторых наборов переменных, называемых в этом случае запрещёнными. На рис.9 отмечены поля из соседних пар наборов переменных, на которых ФАЛ не определена или имеет единичные значения.

Рис.8. Пример построения карт Карно и Вейча для четырёх- и пятиместных наборов переменных

 
 


F= 0Ú2Ú4Ú6Ú12Ú14Ú(16)Ú(20)Ú22Ú24Ú26Ú32Ú34 ;

Коды наборов восьмиричные. На (*) наборах функция не определена.

 

Рис.9. Диаграмма Вейча ФАЛ пяти переменных

 

Соседними являются и наборы, лежащие на границах карты, например: 3-7, 3-13, 3-23, 7-17, 1-11, 5-15, 27-37, 25-35, 21-31, 23-33, 2-22, 12-32.

Для карт с количеством переменных больше четырёх соседними являются наборы, расположенные симметрично относительно соединительной линии (на рис.9 указанной стрелкой) карт меньшего на единицу количества переменных. Например: 1-21, 4-24, 0-20, 14-34, 10-30, 11-31, 15-35.

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

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

 

– Конец работы –

Эта тема принадлежит разделу:

Теория цифровых автоматов

Южно-уральский государственный университет..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Геометрическое представление булевых функций

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Базис И, ИЛИ, НЕ. Свойства элементарных функций алгебры логики
  Пусть x - некоторая логическая переменная. Тогда: 1. , что означает возможность исключения из логического вы

Табличное описание булевых функций
  Вследствие конечности множества наборов заданного количества логических переменных, простейшим и самым естественным способом описания ФАЛ является табличный. Пример описания трёх ФА

Аналитическое описание булевых функций
На примерах описания ФАЛ, приведенных в таблице 3, видно, что конституента 1 может быть описана в виде элементарной конъюнкции переменных:

Минимизация с помощью минимизирующих карт
  Как было отмечено выше, одним из способов представления ФАЛ от небольшого числа переменных (обычно не больше 5) являются диаграммы Карно или Вейча, которые строятся на развёртках мн

Минимизация функций алгебры логики по методу Квайна
  При минимизации по методу Квайна в базисе И, ИЛИ, НЕ исходная ФАЛ задаётся в СДНФ. Целью минимизации является нахождение всех первичных импликант и выбор некоторых из них для

По методу Квайна - Мак-Класки
  Недостаток метода Квайна - необходимость исчерпывающего попарного сравнения или сопоставления всех минтермов на этапе нахождения первичных импликант. С ростом числа минтермов увелич

Логические элементы И и И-НЕ
(Позитивная логика) Схема логического элемента И, построенного на полупроводниковых диодах и резисторе, приведена на рис.10а).

Логические элементы ИЛИ, ИЛИ-НЕ
  Схема логического элемента ИЛИ, построенного на полупроводниковых диодах и резисторе, приведена на рис.12а).

Программируемые логические матрицы (ПЛМ)
  Программируемая логическая матрица [2] представляет собой функциональный блок, созданный на базе интегральной полупроводниковой технологии и предназначенный для реализации логически

Процедуры программирования ПЛМ
Физическим принципом программирования ПЛМ является пережигание (испарение) выбранных перемычек. В процессе эксплуатации ПЛМ могут возникнуть следующие задачи: - начальное программ

Определение абстрактного цифрового автомата
Обобщённая структура системы обработки цифровой информации, приведённая на рис.1, соответствует описанию абстрактного цифрового автомата. Для целей технического проектирования в каноническую структ

Методы описания цифровых автоматов
  Чтобы задать цифровой автомат S, необходимо описать все элементы множества S = { A, X ,Y, d, l, a1}, то есть входной и выходной алфавиты и алфавит состояний, а также функ

Синхронные и асинхронные цифровые автоматы
Состояние as автомата S называется устойчивым состоянием, если для любого входа zfÎX, такого, что d(am, zf) = as, имеет место d(as

Цифровых автоматов Мили и Мура
Абстрактный цифровой автомат работает как преобразователь слов входного алфавита в слово в выходном алфавите [5]. Рассмотрим это положение, взяв в качестве примера автомат Мили S1.

Минимизация абстрактного автомата Мили
  Для табличного описания процедура минимизации цифровых автоматов алгоритмизирована и выполняется в несколько шагов.   Шаг 1 Распространение неопределённости т

Минимизация абстрактного автомата Мура
Минимизация автоматов Мура основана на тех же принципах, что и минимизация автоматов Мили. Для табличного описания эта процедура алгоритмизирована и состоит из трёх шагов.  

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

Синхронизация в цифровых автоматах
  Смена состояний в синхронизированных автоматах происходит в определённые моменты времени, задаваемые по цепям синхронизации внешним тактовым генератором. Изменение состояний в реаль

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

Декомпозиция устройств обработки цифровой информации
  В любом устройстве или системе обработки цифровой информации можно выделить два существенно различающихся блока (рис.63): - операционный блок (или операционный автомат);

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

Принцип действия управляющего автомата с хранимой в памяти логикой и микропрограммное управление
  Хранимая в памяти микропрограмма должна содержать информацию о функциях переходов и выходов управляющего микропрограммного автомата. Рассматривая управляющий автомат (УА) в терминах

Горизонтальное микропрограммирование
  При горизонтальном микропрограммировании каждому биту операционной части микрокоманды ставится в соответствие определённый управляющий функциональный сигнал, то есть определённая ми

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

Горизонтально - вертикальное микропрограммирование
  В этом случае подмножества VL представляются горизонтальным способом , а микрооперации внутри каждого из подмножеств - вертикальным способом (рис.66). Для каждого подмнож

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

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

Синтез микропрограммного автомата Мура
Синтез автомата Мура по граф - схеме алгоритма также состоит из двух этапов: - получение отмеченной ГСА; - построение графа автомата. На первом из этих этапов начальная,

Минимизация микропрограммных автоматов
  Изложенный ранее метод минимизации абстрактных автоматов применяется и для минимизации полностью определённых микропрограммных автоматов. Если два состояния автоматы Мили с

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги