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

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

Минимизация функций алгебры логики по методу Квайна

Минимизация функций алгебры логики по методу Квайна - раздел Транспорт, Теория цифровых автоматов   При Минимизации По Методу Квайна В Базисе И, Или, Не Исходная...

 

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

Импликанта функции - некоторая логическая функция, обращаемая в нуль при наборе переменных, на котором сама функция также равна нулю.

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

Первичная импликанта функции - импликанта типа элементарной конъюнкции некоторых переменных, никакая часть которой уже не является импликантой.

Задача минимизации по методу Квайна решается путём попарного сравнения всех импликант, входящих в ФАЛ, с целью выявления возможности их неполного склеивания по какой-то переменной на промежуточных этапах

; (25)

Из первичных импликант выбираются такие, которые представляют исходную ФАЛ минимальным образом.

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

Минимизация по методу Квайна алгоритмизирована и выполняется в несколько этапов. Рассмотрим применение этого метода минимизации на конкретном примере функции алгебры логики, приведенной в цифровой форме в восьмеричной системе счисления

F= (2)Ú3Ú4Ú5Ú7Ú11Ú13Ú14Ú15Ú(17)=

Э т а п 1. Нахождение первичных импликант. Прежде всего составляется таблица (таблица 4) и находятся импликанты четвёртого и третьего рангов, то есть понижается ранг минтермов, входящих в СДНФ. Затем составляется другая таблица (таблица 5), которая включает все импликанты третьего ранга. По этой таблице находятся импликанты третьего и второго рангов. В общем случае составление таблиц и нахождение термов низшего ранга продолжается до тех пор, пока нельзя будет выполнить склеивание по какой-либо переменной для термов низшего ранга.

 

Таблица 4

  Термы
X                
X X            
X X X          
X X X X        
X X X X X        
X X X X X X    
X X X X X X X    
X X X X X X X X  
X X X X X X X X X
X X X X X X X X X X

 

Примечания:

1). X - ячейка таблицы не заполняется;

2). На всех (*) наборах функция доопределена как имеющая значение 1.

Для уменьшения трудоёмкости заполнения таблицы, заполняются только клетки, лежащие по одну сторону от диагонали таблицы, поскольку результат операции склеивания не зависит от порядка следования склеиваемых термов. По этой таблице определяется правильность доопределения ФАЛ. Если термы неопределённости ФАЛ подверглись склеиванию только друг с другом или вообще не склеились, то на этих наборах следует доопределить ФАЛ, как имеющую нулевые значения. В нашем примере по таблице видно, что ФАЛ требуется доопределить как имеющую единичные значения на наборах 2 и 17. Если какие-то термы не подверглись склеиванию, их следует включить в список первичных импликант и исключить из дальнейшего рассмотрения. В нашем примере не склеивающихся минтермов в ФАЛ нет. Для дальнейшего сопоставления все термы, имеющие ранг на единицу меньший ранга исходных минтермов, из таблицы 4 заносятся в таблицу 5.

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

 

Таблица 5

  Термы
Х                        
  Х                    
    Х                  
      Х                
        Х              
          Х            
            Х          
              Х          
                Х      
                  Х    
                    Х    
                      Х  
                        Х

 

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

Э т а п 2. Расстановка меток. Составляется таблица, число строк которой равно числу полученных первичных импликант, а число столбцов равно количеству минтермов СДНФ. Если в некоторый минтерм СДНФ входит какая-либо из первичных импликант, то на пересечении строки и соответствующего столбца ставится нечисловая метка, например, © (таблица 6).

 

Таблица 6

  Термы
  ©з     ©   ©     ©
    ©с ©       ©с ©  
      © ©       © ©
          ©с ©   © ©
©с ©                

 

Э т а п 3. Нахождение существенных импликант. Если в каком-либо из столбцов таблицы 6 имеется только одна метка, то первичная импликанта в соответствующей строке является существенной, так как без неё не будут получены заданные единичные значения минимизированной ФАЛ на всём множестве заданных минтермов СДНФ ФАЛ. В таблице 6 существенные импликанты отмечены знаком ©с синего цвета. По таблице 6 видно, что пятая первичная импликанта является существенной только для неопределённого минтерма . Если придать СДНФ исходной ФАЛ нулевое значение на наборе переменных , то пятую первичную импликанту нужно исключить, тогда первая импликанта (она отмечена знаком ©з зелёного цвета) станет существенной. На наборе исходной ФАЛ следует придать единичное значение. Столбцы, соответствующие существенным импликантам из таблицы вычёркиваются, а сами существенные импликанты в дальнейшем рассмотрении не используются.

Э т а п 4. Вычёркивание лишних столбцов. После третьего этапа в результате вычёркивания столбцов, соответствующих существенным импликантам, строится новая таблица 7. В эту таблицу включаются оставшиеся столбцы и соответствующие им первичные импликанты. Если в этой таблице есть столбцы, в которых имеются метки в одинаковых строках, то эти столбцы вычёркиваются , кроме одного. Минтерм оставшегося столбца будут покрывать отброшенные минтермы. В нашем примере ФАЛ такого случая нет.

Таблица 7

Существенные первичные импликанты в ячейках таблицы 7 помечены знаком ©с синего цвета.

Э т а п 5. Вычёркивание лишних первичных импликант. Если после вычёркивания лишних столбцов на этапе 4 в таблице 7 появляются строки, в которых нет ни одной метки, то первичные импликанты, соответствующие этим строкам, исключаются из дальнейшего рассмотрения, так как они не покрывают оставшиеся в рассмотрении минтермы. После выполнения этапов 4 и 5 рассматриваемая таблица 6 покрытия минтермов первичными импликантами несколько упрощается.

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

Таким образом, минимальная дизъюнктивная нормальная форма (МДНФ) заданной функции складывается из существенных импликант (этап 3) и первичных импликант, покрывающих оставшиеся минтермы (этап 6). Минимизированная ФАЛ нашего примера запишется как:

F = (27)

Сравнивая фф.(26) и (27), видим, что аналитическая запись минимизированной ФАЛ значительно проще, чем исходная СДНФ ФАЛ.

 

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

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

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

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

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

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

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

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

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

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

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

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

Минимизация с помощью минимизирующих карт
  Как было отмечено выше, одним из способов представления ФАЛ от небольшого числа переменных (обычно не больше 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
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги