КОНСПЕКТ ЛЕКЦИЙ 4 страница

Карты Карно для 3-х и 4-х переменных выглядят так:

Следует обратить внимание на расположение наборов аргументов по координатным осям КК. Последовательность наборов определяется изменением значения только одной переменной. Поэтому расположение 00 01 10 11 является неправильным, т. к. при переходе от 01 к 10 изменяются сразу две переменные. Правильным будет расположение 00 01 11 10.

Задание 49. Представить логическую функцию картой Карно.

Задание 50. Представить логическую функцию картой Карно.

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

Если аргумент х_i в таблице истинности располагать в порядке возрастания индекса i, то наборы аргументов в таблице можно сокращённо обозначать десятичными числами. Тогда СДНФ в цифровой форме будет представлять сумму чисел, соответствующих наборам аргументов на которых функция принимает значение равное единице.

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

Десятичные числа в цифровой форме располагаются в порядке возрастания.

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

При построении F_СДНФ­ в цифровой форме следует выделять в ТИ наборы аргументов 001, 010, 100, 110, 111 и представлять их десятичными числами 1, 2, 4, 6, 7. Тогда

При построении F_CКНФ в цифровой форме выделяем наборы 000, 011, 101, заменяем их на обратные, т. е. на 111, 100, 010 и представляем их десятичными числами 7, 4, 2, располагая по возрастанию:

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

При цифровых формах представления логических функций переход от СДНФ к СКНФ или наоборот выполняется по следующим правилам.

Пусть задана функция

Перейдём к обратной функции где N – полное количество наборов аргументов функции. Обратная функция получается путём записи в неё десятичных чисел, отсутствующих в представлении F­_СДНФ. Используя можно получить , где

Пример. Для функции, рассмотренной в предыдущем примере, выполнить переход от F_СДНФ к F­_СКНФ в цифровой форме.

Задана

Перейдём к обратной функции: Так как N=8, то

Следовательно,

Задание 51. Представить логическую функцию F₁, заданную таблицей истинности (табл. 3), в цифровых формах.

Задание 52. Представить логическую функцию F₂, заданную таблицей истинности (табл. 3), в цифровых формах.

Задание 53. Представить в цифровых формах

Задание 54. Представить в цифровой форме и выполнить переход к F_СКНФ.

Задание 55. Представить

в цифровой форме и выполнить переход к F_СДНФ.

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

Строчное представление целесообразно при обработке логических функций на ЭВМ. При таком представлении столбец значений функции из таблицы истинности записывается горизонтально – строчкой и выделяется рамкой.

Пример. Представить функцию F­₁ (таблица 3) в строчной форме.

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

Пример. Представить функцию, заданную цифровыми формами

в строчных формах.

Как видно из примера, единицы при строчной записи расположены в разрядах, соответствующих десятичным числам при цифровой записи.

Задание 56. Представить функцию F₂ (табл. 3) в строчной форме и выполнить переход к цифровой форме представления.

Задание 57. Представить функцию в строчной форме.

1.3.3. Минимизация логических функций.

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

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

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

Минимизация методом Карно (рассмотрим три варианта: А, Б, В).

А. Минимизация в дизъюнктивно нормальной форме (получение МДНФ).

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

Группой клеток называется совокупность соседних клеток, составляющих прямоугольник размерности где а и b = 0, 1, 2, ….

Каждой группе размерности соответствует конъюнкция состоящая из переменных, где n – полное число аргументов логической функции. В конъюнкцию включаются все аргументы, значения которых не изменяются в пределах соответствующей группы. Если переменная в пределах группы равна 0, то она входит в конъюнкцию с инверсией, а если 1 – без инверсии.

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

Два принципа формирования группы:

- каждая группа должна быть как можно больше, т. е. max(a+b);

- число групп должно быть как можно меньше.

Пример. Дана карта Карно для функции 4-х переменных. Получить МДНФ этой функции.

Например, конъюнкция соответствующая 1-ой группе состоит из двух аргументов, т. к. , а для 2-ой группы .

Следует обратить внимание, что группы могут пересекаться, т. е. одна и та же 1-ца может входить в разные группы.

В КК для 3-х и 4-х переменных клетки могут объединяться в так называемые разорванные группы, например:

Пример. Дана карта Карно для функций 4-х переменных. Получить МДНФ этой функции.

Задание 58. Получить МДНФ для функции F₁ заданной в таблице 4.

Задание 59. Получить МДНФ для функции F₂ заданной в таблице 4.

Б. Минимизация в конъюнктивной нормальной форме (получение МКНФ).

Здесь возможны 2 способа.

1. Перейти от МДНФ к МКНФ при помощи правила Де Моргана.

2. Использовать клетки КК содержащие нули.

Составление МКНФ заключается в объединении конъюнкциями дизъюнкций, соответствующих всем выделенным группам. В дизъюнкцию включаются все переменные, значения которых не изменяются в пределах группы. Причём, если переменная в пределах группы равна 0, то она входит в дизъюнкцию без инверсии, а если равна 1, то с инверсией.

Пример. Дана карта Карно для функции 4-х переменных. Получить МКНФ этой функции.

Задание 60. Получить МКНФ для функции F₄ заданной в таблице 4.

Задание 61. Получить МКНФ для функции F₃ заданной в таблице 4.

В. Минимизация неполностью определённых функций.

Неполностью определённые функции это такие функции, которые определены не на всех 2ⁿ наборах аргументов.

На карте Карно неопределённое условие обозначается прочерком (-). Клетки с прочерком могут произвольным образом включаться в группы, как при построении МДНФ, так и при построении МКНФ. Более того, их можно вообще никуда не включать (игнорировать).

Пример. Дана карта Карно для функции 4-х переменных. Получить МДНФ и МКНФ этой функции.

Задание 62. Получить МДНФ для функции F₅ заданной в таблице 4.

Задание 63. Получить МДНФ и МКНФ для функции F₆ заданной в таблице 4.

Минимизация методом Морреля.

В основе метода лежит теорема разложения.

Теорема разложения. Любую логическую функцию от n переменных можно свести к двум функциям от (n-1) переменных, проведя разложение вида

Сущность метода заключается в последовательном разложении функции по переменным и в анализе остаточных функций на равенство их нулю или единице.

Если остаточная функция равна нулю, то член, её включающий, равен нулю и исключается из разложения. Если остаточная функция равна единице, то переменная или конъюнкция переменных, связанных с ней, входит в тупиковую форму, а член из дальнейшего рассмотрения исключается. Все оставшиеся после анализа остаточные функции разлагаются по следующей переменной и снова анализируются и т. д. Минимизация заканчивается когда все остаточные функции будут равны 0 или 1.

Для получения формы, наиболее близкой к минимальной, Моррель предложил в формулу разложения добавить так называемый «терм Морреля», который добавляется всякий раз при разложении по любой переменной.

Формула разложения примет вид:

Покажем, что терм Морелля не изменит функцию:

.

При анализе остаточных функций на каждом этапе разложения проверяются условия поглощения термом Морреля других остаточных функций.

Минимизацию методом Морреля удобно проводить над функцией представленной в строчной форме (т. к. метод реализуем на ЭВМ). Разложение функции, представленной в строчной форме, по переменной х_i означает её разбиение на две части. В первую часть входят те наборы, на которых х_i=0, а во вторую – на которых х_i=1.

Пример. Пусть задана функция F(A,B,C,D) в строчной форме.

. Выполнить разложение функции по переменной А.

.

Теперь получим терм Морреля и добавим в разложение.

Следовательно,

Пример. Минимизировать методом Морреля функцию

.

Таким образом, получим F(A,B,C,D)=A+C.

Задание 64. Выполнить разложение функции F₁ (таблица 3) по переменной х₁.

Задание 65. Минимизировать функцию F₂ (таблица 3) методом Морелля.

Задание 66. Минимизировать функцию методом Морреля.

1.4. Синтез и анализ комбинационных схем.

Устройство, осуществляющее дискретное преобразование информации ЭВМ, называется автоматом. Существуют два основных вида дискретных автоматов: комбинационные автоматы (схемы) и конечные автоматы.

Введём: Х(t)={x₁, x₂, …, x_i, …, x_n} – множество входных дискретных сигналов; .

Y(t)={y₁, y₂, …, y_j, …, y_m} – множество выходных дискретных сигналов; .

Здесь t – дискретное время, определяется моментами перехода автомата из одного состояния в другое.

Определение. Если совокупность выходных сигналов (выходного слова) Y(t) зависит только от совокупности входных сигналов (входного слова) X(t) и не зависит от внутренних состояний автомата, то такой автомат называется комбинационным автоматом (комбинационной схемой).

Структурная схема комбинационного автомата:

Здесь Р – функция преобразования.

Закон функционирования комбинационной схемы определяется заданием соответствия между её входными и выходными словами Y(t)=P[X(t)] и может быть дан таблицей истинности, в аналитический форме и др.

1.4.1. Алгоритм синтеза комбинационной схемы.

1. Задать закон функционирования комбинационной схемы.

2. Провести минимизацию функции преобразования Р, получить Р_МДНФ и Р_МКНФ.

3. Преобразовать Р_МДНФ и Р_МКНФ в соответствии с заданным базисом логических функций (используемыми логическими элементами) и выбрать наиболее компактную форму представления Р.

4. Построить функциональную схему устройства.

5. Выполнить схемотехническую коррекцию схемы с учётом характеристик и параметров используемых логических элементов:

- коэффициента объединения (количество входов элемента),

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

- уровня логических 0 и 1,

- помехозащитности и др.

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

1.4.2. Функциональные схемы логических элементов.

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

дизъюнкция («или»)

конъюнкция («и»)

инверсия («не»)

(здесь и в дальнейшем будет употребляться закрашенный кружок в обозначении инверсии вместо не закрашенного как принято)

стрелка Пирса («или-не»)

штрих Шеффера («и-не»)

Свести 3-х и 4-х входовые логические схемы к 2-х входовым можно следующим образом:

«3 и»

«3 или»

«4 и»

«4 или»

«3 и-не»

«3 или-не»

«4 и-не»

«4 или-не»

1.4.3. Пример синтеза полного одноразрядного двоичного сумматора.

Пример. Синтезировать схему полного одноразрядного двоичного сумматора используя двухвходовые логические элементы, реализующие логическую функцию «и-не».

Представим сумматор в виде:

a и b – одноразрядные двоичные слагаемые.,

с – перенос из младшего разряда,

S – сумма,

Р – перенос в старший разряд.

S=F₁(a,b,c), P=F­₂(a,b,c).

При синтезе реализуем последовательно этапы алгоритма.

1. Зададим закон функционирования сумматора в виде ТИ.

2. Проведём минимизацию функций S и Р методом Карно. По ТИ составим карты Карно:

Проверим предварительное построение схем сумматора непосредственно по выражениям S_МДНФ и Р_МДНФ без преобразования их к заданным двухвходовым элементам «и-не».

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