Понятие минимизации логических функций

При представлении функции алгебры логики (ФАЛ) математическим выра­жением используют два вида ее представления.

Дизъюнктивной нормальной формой (ДНФ) на­зывается логическая сумма элементарных логических произведе­ний, в каждое из которых аргумент или его отрицание входят один раз.

ДНФ может быть получена из таблицы истинности сле­дующим образом: для каждого набора аргументов, на котором функция равна «1», записывают элементарные произведения пе­ременных, причем переменные, значение которых равно нулю, записывают с инверсией. Полученные произведения, называемые минтермами, суммируют.

Конъюнктивной нормальной формой (КНФ) на­зывается логическое произведение элементарных сумм, в каждую из которых аргумент или его отрицание входят один раз. КНФ может быть получена из таблицы истинности: для каждого набора аргументов, на котором функция равна «0», составляют элемен­тарную сумму, причем переменные, значение которых равно «1», записываются с отрицанием. Полученные суммы объединяют опера­цией логического умножения.

 

Пример 1 Таблица 1.2 — Таблица истинности

x2	x1	x0	y

Задана логическая функция 3-х переменных, которая равна единице в случае, если хотя бы две из входных переменных рав­ны единице. Запишем эту функцию в виде таблицы истинности (табл. 1.2). Для данной логической функции ДНФ имеет вид

ДНФ, полученная суммированием конституента единицы, на­зывается совершенной (СДНФ).

Для функции из примера 1 КНФ:

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

Минимизация ФАЛ — сокращение логического выражения функции до минимума. Целью минимизации является миними­зация стоимости ее технической реализации.

Метод минимизации ФАЛ с использованием карт Вейча (Кар­но) базируется на табличном виде представления ФАЛ. Картой Вейча (Карно) называется таблица, число клеток ко­торой для функции и переменных равно 2ⁿ, причем каждому минтерму соответствует своя клетка карты (рис. 1.15).

Рисунок 1.15 — Вид карты Вейча (Карно) для функции 3 переменных

Если требуется представить на карте Вейча (Карно) логичес­кую функцию, заданную в виде ДНФ, в соответствующие клет­ки заносятся единицы. Остальные клетки остаются незаполненными или заполняются нулями. Логиче­ская функция на карте Вейча (Карно) представляется совокупностью клеток, за­полненных единицами, а инверсия функ­ции представляется совокупностью пустых или заполненных нулями клеток.

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

 

Основным критерием минимизации ФАЛ является кри­терий уменьшения количества элементарных логических элемен­тов при использовании только однородных элементов, например, только типа И-НЕ (ИЛИ-НЕ).

Алгоритм минимизации сводится к следующему:

На карте Вейча выделяют прямоугольные области, объединяющие выбранные значения функции («1» или «0»). Причем каж­дая область должна содержать 2^k клеток, где k может принимать значения 0; 1; 2; 3, т.е. 1; 2; 4; 8 клеток. Выделенные области могут пересекаться, т. е. одна клетка может входить в не­сколько разных областей.

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

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

Сумма полученных произведений образует минимальную ДНФ.

При объединении клеток с нулевыми значениями ФАЛ полу­чим ФАЛ, инверсную заданной.

Пример 2

;

 

Пример 3

;

объединяем по «1»

;

 

Следует также отметить, что, поскольку карты Вейча (Карно) функции 3-х переменных представляют собой объемные фигу­ры, при формировании областей необходимо помнить, что в одну область объединяются крайние столбцы карты 3-х переменных (рис. 1.15).

Рисунок 1.16 — Объединение крайних областей в единую область

 

Регистр — электронное устройство, предназначенное для кратковременного хранения и преобразования многоразрядных двоич­ных чисел. Регистр состоит из триггеров, количество которых определяет, сколько разрядов двоичного числа может хранить регистр – разрядность регистра (рис. 1.16, а). Для организации работы триггеров могут быть использованы логические элементы.

Рисунок 1.17 — Регистр

а) общее представление, б) условно-графическое обозначение

По способу ввода и вывода информации регистры подразделяются на параллельные и последовательные.

В последовательном регистре триггеры соединены последовательно, т. е. выходы предыдущего триггера передают информацию на входы последующего. Тактовые входы С триггеров соединены параллельно. Такой регистр имеет один информационный вход и вход управления - тактовый вход С.

В параллельном регистре запись в триггеры происходит одновременно, для чего имеется четыре информационных входа.

На рисунке 1.17 представлено УГО и назначение выводов четырёхразрядного параллельно-последовательного регистра.

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

Счетчики импульсов являются разновидностью регистров (счетные регистры) и строятся соответственно на триггерах и логических элементах.

Основными показателями счетчиков являются коэффициент счета К 2ⁿ - число импульсов, которое может быть сосчитано счетчиком. Например, счетчик, состоящий из четырех триг­геров, может иметь максимальный коэффициент счёта 2⁴=16. Для четырехтриггерного счетчика минимальный выходной код - 0000, максимальный -1111, а при коэффициенте счёта К_с = 10 выходной счет останавливается при коде 1001 = 9.

На рисунке 1.18 представлены УГО четырехразрядного счетчика и временные диаграммы работы. При поступлении первого счетного импульса по его спаду первый триггер переходит в состояние Q1 = 1, т.е. в счетчике записан цифровой код 0001. По окончании второго счетного импульса первый триггер переходит в состояние «0», а второй переключается в состояние «1». В счет­чике записывается число 2 с кодом 0010.

 

Рисунок 1.18 — Двоичный четырехразрядный счетчик

а) условно-графическое обозначение, б) временные диаграммы работы

Подсчет числа импульсов является наиболее распространенной операцией в устройствах цифровой обработки информации.

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