Логические основы проектирования цифровых устройств

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

1.Синтеза.

2. Анализа.

Синтез - это процесс построения схемы цифрового устройства по заданию.

Анализ - процесс обратный синтезу.

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

В общем случае, модель представляет собой многополюсный черный ящик с mвходами иnвыходами (рис.1.3). Состояние автомата определяется состояниями сигналов на его входах и выходах. Совокупность входных и выходных переменных Х и Z образуют входное и выходное слово автомата, соответственно.

Различные значения входных переменных образуют алфавит (т.к. алфавит входных и выходных переменных един, в дальнейшем будет рассматриваться только один алфавит). В цифровой технике алфавит входного (выходного) слова содержит два значения (две буквы) "1" и "0".

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

Основы алгебры логики

Алгебра логики (АЛ) является основным инструментом синтеза и анализа дискретных автоматов всех уровней.АЛназывают также Булевой алгеброй.АЛбазируется на трёх функциях, определяющих три основные логические операции.

1. Функция отрицания(НЕ). f1 =`X читается, как f1 есть (эквивалентна)НЕХ. Элемент, реализующий функциюНЕ,называется элементомНЕ(инвертором).

Элемент НЕимеет два состояния.

2. Функция логического умножения(конъюнкции). Функция логического умножения записывается в виде f2=X₁·X₂. Символы логического умножения &,L, <×>,´. Функция конъюнкции читается так: f2есть(эквивалентна) Х₁иХ₂, поскольку функция истинна тогда, когда истинны 1-й и 2-й аргументы (переменные).Конъюнкциюназывают функциейИ, элемент, реализующий эту функцию, элементомИ.

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

Количество переменных (аргументов), участвующих в одной конъюнкции, соответствует количеству входов элементаИ.

3. Логическое сложение(дизъюнкция). Функция логическогосложениязаписывается в виде f3=X1 + X2, и читается так: f3естьХ1илиХ2, поскольку функция истинна, когда истинна одна или другая переменная (хотя бы одна). Поэтому функцию дизъюнкции часто называют функциейИЛИ. Символы логического сложения +,V.

В общем случае функция ИЛИзаписывается:

Используя операции (функции)И,ИЛИ,НЕможно описать поведение любого комбинационного устройства, задав сколь угодно сложное булево выражение. Любое булево выражение состоит из булевых констант и переменных, связанных операциямиИ,ИЛИ, НЕ.

Пример булева выражения:

.

Основные законы алгебры логики.Основные законы АЛпозволяют проводить эквивалентные преобразования функций, записанных с помощью операций И,ИЛИ,НЕ, приводить их к удобному для дальнейшего использования виду и упрощать запись.

ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ Таблица 1.1

N	а	б	Примечание
	=1 X+0=X X+1=1 X+X=X X+ =1	=0 X*1=X X*0=0 X*X=X X* =0	Аксиомы (тождества)
	=X		Закон двойного отрицания
	X+Y=Y+X	X*Y=Y*X	Закон коммутативности
	X+X*Y=X	X =X	Закон поглощения
	= *		Правило де-Моргана (закон дуальности)
	+Z=X+Y+Z		Закон ассоциативности
	X+Y*Z=		Закон дистрибутивности

Булевой алгебре свойственен принцип двойственности, что наглядно иллюстрирован в табл. 1.1. Как следует из табл. 1.1, только закон двойного отрицания не подчиняется этому принципу.

Используя законы алгебры логики, можно упростить булевы выражения, в частности, правило склеивания позволяет упростить выражение типа

.

Действительно, используя законы 2, 5 и 11 можно записать исходное выражение в виде Х₂(Х₁+`Х<sub>1</sub>) =Х<sub>2</sub>. Так как логическая операция Х<sub>1</sub>+`Х₁= 1 (см. з-н 5), а Х₂×1 = Х₂(см. з-н 2б), полученное выражение истинно.

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

Поскольку дискретный автомат имеет конечное число входов, то мы будем иметь дело с функцией конечного числа аргументов. Если автомат имеет m входов, то количество входных переменных тоже m и число возможных комбинаций наборов значений этих входных аргументов (переменных) К=2^m.

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

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

Таблица истинности содержит 2^mстрок,mстолбцов (по количеству входов) и один столбец для записи значения функции.

Например: пусть требуется задать функцию трех переменных F1(Х1,Х2,Х3) (рис. 1.4), т.е. автомат на три входа и на один выход, следовательно, M=3, К=8.

Следующий способ задания дискретного автомата – числовой.В Этом случае функция задается в виде десятичных эквивалентов номеров наборов аргументов, при которых функция принимает единичное значение. Например, для рассмотренного выше примера функция F1 принимает единичные значения на наборах переменных со следующими номерами: 1, 2, 5, тогда числовой способ задания будет иметь вид

.

Координатный способ. При этом способе дискретный автомат задается с помощью карты его состояния, которая известна каккарта Карно.

Карта Карно содержит 2^mклеток по числу наборов значений переменных. Каждая клетка определяется координатами строк и столбцов, соответствующими определенному набору переменных. Все входные переменные разбиваются на 2 группы так, что одна группа определяет координаты строк, а другая - координаты столбцов. В каждой клетке карты Карно проставляется соответствующее значение функции на заданном наборе. Пример задания функции трех переменных приведен на рис. 1.5. Числовое выражение этой функции выглядит так:

Пример построения карты Карно для функции 4-х переменных. Пусть функция задана в числовой форме и имеет вид:

,

следовательно, К=16, m=4.

Сначала проводим разметку координат карты Карно без указания значений функции. Для удобства воспользуемся указанием "шапки" в виде прямых линий, “под” которыми переменные входят в значение координат без отрицания (рис.1.6). Таким образом, по столбцам и по строкам переменные входят без отрицания в пределах линии-шапки.

Для наглядности координаты клеток карты Карно указаны в трех формах: в виде наборов переменных; в виде двоичного числа, соответствующего порядковому номеру набора переменных; в десятичном эквиваленте номеров наборов переменных. На практике координаты внутри клеток не записывают (рис. 1.7), в клетках указываются единичные значения функции, соответствующие “координатным” наборам переменных. Нулевые значения функции в клетки можно не записывать, т.е. клетки, координаты которых определяются наборами переменных с нулевыми значениями функции, можно оставить пустыми.

Следует отметить, что перестановка местами переменных Х1 и Х2, а так же переменных Х3 и Х4 допускается, допускается также перестановка местами переменных Х1Х2 и Х4Х3. При построении карты Карно, т.е. при задании логической функции, указывают лишь внешние элементы разметки координат (рис. 1.7).

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

Например: .

Совершенная нормальная дизъюнктивная форма(СНДФ). По таблице истинности можно составить логическое выражение, содержащее наборы переменных, в которые входят все переменные с отрицанием или без. Одна из его форм называется СНДФ.

В качестве примера получения СНДФ рассмотрим случай задания логической функции в виде таблицы истинности. Пусть задана функция трех переменных. Таблица истинности этой функции показана на рис. 1.8. (очевидно, что значения функции взяты произвольно и могут быть любыми).

Из таблицы истинности видно, что функция принимает значение логической единицы только на трех наборах переменных, т.е. на 2, 4 и 5-м наборах. Для второй строки (второго набора переменных) можно записать: Х1=0, Х2=1, Х3=0, следовательно, функция f(0,1,0)=1. Принято (по умолчанию) считать, что если переменная в "нормальном" состоянии имеет значение логической единицы, а в инверсном - логического нуля, тогда функцию для второй строки можно представить в виде `X<sub>1</sub>Х<sub>2</sub>X<sub>3</sub>= 1. Для четвертой строки -`X₁X₂Х₃= 1 и для пятой строки - Х₁X₂Х₃= 1. Аналитическое выражение функции выглядит как

.

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

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