Теория дискретных систем автоматики и телемеханики 3 страница

После выполненных склеиваний остались следующие термы: , ; ; ; .

Теперь переходим ко второму этапу и подвергаем всевозможные из выписанных пар термов поглощению (в нашем примере возможно только одно поглощение): + = . Таким образом, результатом выполнения двух этапов метода являются три следующих терма: ; ; .

Приступим теперь к построению таблицы покрытия (последний шаг метода), в которой эти термы помещаются в заголовки строк, а конституенты ФАЛ - в заголовки столбцов. Структура таблицы ясна из рисунка:

Констиуенты Термы
	*	*	*	*
					*	*
				*		*

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

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

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

В нашем примере, как легко убедиться, строки, соответствующие термам и , покрывают все столбцы таблицы. Следовательно, минимальной ДНФ рассматриваемой ФАЛ является = + .

5.3. Минимизация с помощью карт Карно.

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

Преимуществом карт Карно является простота обнаружения возможных упрощений ФАЛ. Опишем метод минимизации ФАЛ в форме СДНФ на примере функции, представленной на рис.1.

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

Рис.1.Таблица истинности (а) и соответствующая ей карта Карно (б) для функции F

.

Минимизация ФАЛ с помощью карты Карно сводится к объединению клеток в блоки. В блок можно объединить только клеток, где n=1,2,3,…(Так, блок не может содержать, например, 6 клеток, т.к. при любом ). В случае минимизации ФАЛ, заданной в виде СДНФ, все клетки, объединяемые в блок, должны быть соседними и содержать 1 ( наличие 0 между клетками блока не допускается). Блок из двух клеток – это прямоугольник из единиц, расположенных по горизонтали или вертикали; блок из 4-х клеток - может быть прямоугольником из единиц, расположенных по горизонтали или вертикали, а также квадратом размера 2 2 и т.д. За счет объединения клеток в блоки и происходит минимизация ФАЛ. Так, блок из двух клеток (он соответствует логической сумме двух конституент единицы) будет заменен одним термом, у которого число переменных уменьшится на 1, блок из 4-х клеток даст один терм с числом переменных на 2 меньше и т.д.

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

Обратимся к нашему примеру. На рис.1б изображены 4 блока, которыми покрыты все единицы карты Карно (можно убедиться, что для нашего примера покрытия с меньшим числом блоков не существует) :

Блок I – содержит 4 единицы, расположенные по вертикали в столбце 00;

Блок II - содержит 2 единицы, расположенные по горизонтали в строке 00;

Блок III - содержит 4 единицы, образующие квадрат;

Блок IV - содержит 4 угловые единицы в карте Карно. В последнем блоке все клетки действительно являются соседними, т.к. карту можно сворачивать в цилиндр как по горизонтали, так и по вертикали.
Заметим. что в общем случае минимальное покрытие не единственно, т.е. для одной и той же ФАЛ могут существовать различные ее минимальные формы.

Произведем теперь склеивание, например, в блоке II: В результате получился один терм с тремя переменными, общими для входящих в обе конституенты. После склеивания в блоке I получится терм . Для блока III, имеющего квадратную форму и состоящего также из четырех клеток, получим конъюнкцию АС. Для блока IV получим конъюнкцию . Таким образом, с помощью карты Карно найдена минимальная форма рассмотренной ФАЛ: .

Рассмотрим теперь вопрос о минимизации ФАЛ, заданной в форме СКНФ. Отметим, что принципы минимизации остаются теми же, что и в случае представления функции в форме СДНФ. В карте Карно для случая СКНФ каждая клетка имеет точно такие же координаты, как и в случае СДНФ. Каждой координате соответствует клетка, а клетке соответствует набор переменных (макстерм), на котором ФАЛ принимает значение 0. Именно это значение и записывается в соответствующую клетку.

В качестве примера рассмотрим минимизацию следующей ФАЛ, заданной в форме СКНФ:

Построим карту Карно этой функции:

В случае СКНФ в блоки будут объединяться клетки с нулевыми значениями ФАЛ. В нашем примере покрытие всех нулей в карте Карно блоками максимального размера реализуется тремя блоками (далее координаты каждой клетки в блоке указаны по аналогии с индексами элементов матрицы размерности 4 4, представляющей карту Карно):

Блок 1 (4клетки): (1,1) ,(1,2),(2,1), (2,2) - обозначены красным цветом;

Блок 2 (4клетки): (2,3) ,(2,4),(3,3), (3,4) - обозначены синим цветом;

Блок 3 (2 клетки): (1,1)(4,1) –обозначены зеленым цветом.

В блоке 3 первая клетка входит также и в блок 1.

В блоке 1 все макстермы содержат две одинаковых переменных ; следовательно, после склеивания получится макстерм ( ), который будет входить в минимальную КНФ рассматриваемой функции;

В блоке 2 все макстермы содержат две одинаковых переменных ; следовательно, после склеивания получится макстерм ( ), который также будет входить в минимальную КНФ рассматриваемой функции;

В блоке 3 все макстермы содержат три одинаковых переменных ; следовательно, после склеивания получится макстерм ( ), входящий в минимальную КНФ.

Таким образом, с помощью карты Карно найдена минимальная форма рассмотренной ФАЛ в форме КНФ:

Если рассмотренная нами ФАЛ будет задана в форме СДНФ, то после ее минимизации, как можно убедиться, будет получена следующая минимальная ДНФ:

Сравним между собой эти две минимальные формы: обе они содержат одинаковое число термов (по 3), при этом минимальная КНФ содержит 7 переменных, а минимальная ДНФ содержит 8 переменных.

6.Синтез комбинационных дискретных устройств.

Синтез состоит в построении принципиальной схемы комбинационных дискретных устройств (КДУ) по заданному словесному описанию его алгоритма работы. Он реализуется в несколько этапов:

1.Вводятся входные переменные и выходные функции (выбираются их обозначения).

2.В этих обозначениях составляется таблица истинности выходной ФАЛ (или несколько таблиц, если КДУ должно реализовать несколько функций).

3.ФАЛ записывается в базисе И, ИЛИ, НЕ.

4. Производится минимизация ФАЛ в этом базисе.

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

В качестве примера синтезируем для трехразрядного числа преобразователь из прямого кода (традиционная запись двоичного числа) в дополнительный. Дополнительный код числа образуется путем прибавления 1 к младшему разряду обратного кода числа (он получается путем инвертирования цифр прямого кода). Например, пусть число А = 10110 (его старший разряд крайний слева). Тогда обратный код для А равен 01001, а дополнительный код равен 01010.

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

Запишем на основе этой таблицы (точнее, трех таблиц истинности, совмещенных в одной) ФАЛ в форме СДНФ, которые должны осуществлять нужное преобразование:

0
1

, ,

.

Для каждой из этих ФАЛ построим карты Карно:

Для

Для

0
1

Для

Минимизируя эти функции с использованием карт Карно, получим следующие ДНФ:

; ; .

По этим структурным формулам можно построить принципиальную схему преобразователя в классическом базисе И, ИЛИ, НЕ.

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

,

.

Теперь можем синтезировать схему преобразователя по полученным функциям:

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

7. Синтез специальных комбинационных устройств

Среди комбинационных устройств выделяются типовые, наиболее широко используемые на практике.

Шифратор — это устройство, преобразующее десятичные числа в двоичную систему счисления, причем каждому входу может быть поставлено в соответствие десятичное число, а набор выходных логических сигналов соответствует определенному двоичному коду. Шифратор иногда называют «кодером» (от англ. coder) и используют, например, для перевода десятичных чисел, набранных на клавиатуре кнопочного пульта управления, в двоичные числа. Так, для преобразования кода кнопочного пульта в четырехразрядное двоичное число достаточно использовать лишь 10 входов.

Рассмотрим пример построения шифратора для преобразования десятиразрядных десятичных цифр от 0 до 9 в двоичный код. При этом предполагается, что сигнал, соответствующий логической единице, в каждый момент времени подается только на один вход . Условное обозначение такого шифратора и таблица соответствия кода приведены ниже.

Используя приведенную ниже таблицу соответствия, запишем ФАЛ, которые реализуются на выходах шифратора. Нажатие кнопки 8 на клавиатуре шифратора эквивалентно тому, что его входной сигнал . Четырехразрядное двоичное представление числа 8 есть 1000, т.е. на выходах шифратора должны быть сигналы . Аналогично, нажатие кнопки 9 на клавиатуре должны инициировать сигналы на выходах шифратора .Поскольку в представленной таблице соответствия только для цифр 8 и 9, следовательно, ФАЛ для этого выхода есть . Рассуждая далее таким же образом, нетрудно убедиться, что , , .Таким образом, представленная таблица соответствия есть не что иное как совокупность 4-х таблиц истинности ФАЛ, реализуемых на выходах шифратора.

Десятичное число	Двоичный код 8421
x8	x4	x2	x1
0
1
2
3
4
5
6
7
8
9

Представим на рисунке схему такого шифратора, используя элементы ИЛИ.

Дешифратор– используетсядля обратного преобразования двоичных чисел в небольшие по значению десятичные числа. Это ДУ называют также декодером. Входы дешифратора предназначаются для подачи двоичных чисел, выходы последовательно нумеруются десятичными числами. При подаче на входы двоичного числа появляется сигнал на определенном выходе, номер которого соответствует входному числу.

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

На рис. ниже приведено символическое изображение дешифратора.

Символ DС образован из букв английского слова DECODER. Слева показаны входы, на которых отмечены весовые коэффициенты двоичного кода. Справа - выходы, пронумерованные десятичными числами, соответствующими отдельным комбинациям входного двоичного кода. На каждом выходе образуется 1 при строго определенной комбинации входного кода. Рассмотрим построение дешифратора, осуществляющего преобразование, заданное следующей таблицей.

.

Значения выходных переменных определяются логическими выражениями (1) либо (2). При выполнении дешифратора на элементах И-НЕ (см. рис. ниже) пользуются (2), получая инверсии выходных функций. В этом случае каждой комбинации входного кода будет соответствовать 0 на строго определенном выходе, на остальных выходах устанавливается 1.

(1) (2)

Мультиплексор - является устройством, которое осуществляет выборку одного из нескольких входов и подключает его к своему выходу. Мультиплексор имеет несколько информационных входов (D₀, D₁, ...), адресные входы (А₀ А₁, ...), вход для подачи синхронизирующего сигнала С и один выход Q. На рисунке ниже показано символическое изображение мультиплексора с четырьмя информационными входами ( ) и его принципиальная схема ( ) .

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

Таким образом, подавая на адресные входы адреса различных информационных входов, можно передавать цифровые сигналы с этих входов на выход Q. Очевидно, число информационных входов n и число адресных входов связаны соотношением n = .

Функционирование мультиплексора определяется приведенной таблицей. При отсутствии синхросигнала (C = 0) связь между информационными входами и выходом отсутствует (Q = 0). При подаче синхросигнала (C = l) на выход передается логический уровень того из информационных входов D_i, номер которого i в двоичной форме задан на адресных входах. Так, при задании адреса A_lA₀ = ll₂ = 3₁₀ на выход Q будет передаваться сигнал информационного входа с адресом 3₁₀, т. е. D₃.