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




В результате вычеркивания столбцов (1,2,3,4,7,8) получается новая модифицированная таблица:

    Первичн            
    импл.-ты        
    +          
    + +        
               
      +        

 

Если в таблице есть два столбца, в которых имеются метки в одинаковых строках, то один из них вычеркивается. Покрытие оставшегося столбца будет осуществлять оставшийся минтерм.

Вычеркивание лишних первичных импликант.

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

Выбор минимального покрытия.

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

Минимальная форма заданной функции складывается из суммы существенных импликант (см. п. 3) и первичных импликант, покрывающих оставшиеся минтермы (п. 6).

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

 

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

Если записать минтермы в виде их двоичных номеров, то все номера можно разбить по числу единиц в этих номерах на пересекающиеся группы. При этом в i-ю группу войдут все номера, имеющие в своей двоичной записи ровно i единиц. По парное сравнение можно производить только между соседними по номеру группами, так как только эти группы отличаются для входящих в них минтермов в одном разряде. При образовании минтермов с рангом выше нулевого в разряды, соответствующие исключенным переменным пишется знак Х. Такая модификация на практике чрезвычайно удобна, так как позволяет избежать выписывания громоздких минтермов и импликант, заменяя эту процедуру выписыванием их двоичных номеров.

Пример. Минимизировать методом Квайна - Мак - Класки ФАЛ:

=

Записываем эти минтермы по группам в двоичном коде:

Нулевая группа      
Первая группа      
Вторая группа      
Третья группа      
Четвертая группа      

 

Сравнивая соседние группы получаем минтермы 3-го ранга:

Нулевая группа 000X    
Первая группа X001    
Вторая группа 011X X110 10X1
Третья группа X111 111X 1X11

 

Теперь находим минтермы 2-го ранга:

Нулевая группа 000X    
Первая группа X001    
Вторая группа X11X X11X 10X1

 

Составляется таблица меток:

                 
000X + +            
X001   +     +      
X11X     + +     + +
10X1         +      

Отсюда получаем:

.

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-02-16 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: