Минимизация логических функций методом Квайна

ВВЕДЕНИЕ

Разработка любого радиоэлектронного устройства сопровождается физичес­ким или математическим моделированием. Физическое моделирование связано с большими материальными затратами, поскольку требуется изготовление макетов и их трудоемкое исследование. Часто физическое моделирование просто невозможно из-за чрезвычайной сложности устройства, например, при разработке больших и сверхбольших интегральных микросхем. В этом случае прибегают к математическо­му моделированию с использованием средств и методов вычислительной техники. Например, известный пакет P-CAD содержит блок логического моделирования цифровых устройств, однако для начинающих, в том числе и для студентов, он пред­ставляет значительные трудности в освоении. Не меньшие трудности встречаются и при использовании системы DesignLab.

Поскольку данное учебное пособие предназначено для студентов младших курсов, еще не получивших углубленные знания в специальных дисциплинах, в качестве основного инструмента­рия для выполнения лабораторных и курсовых работ авторами пособия рекомендуется программа Electro-nics Workbench (EWB) как отличающаяся самым простым и легко осваиваемым пользовательским интерфейсом.

Electronics Workbench (EWB) — разработка фирмы Interactive Image Technologies (www.interactiv.com). Особенностью программы является наличие кон­трольно-измерительных приборов, по внешнему виду и характеристикам прибли­женных к их промышленным аналогам. Программа легко осваивается и достаточно удобна в работе. После составления схемы и ее упрощения путем оформления подсхем моделирование начинается щелчком обычного выключателя.

Для выполнения заданий контрольной работы студенту необходимо либо взять установочные файлы EWB у администратора локальной сети 3 корпуса либо скачать версию 5.12 с официального сайта.

Собранные схемы в формате EWB необходимо предъявить преподавателю после проверки контрольной работы во время зачета.

1. СИНТЕЗ КОМБИНАЦИОННЫХ УСТРОЙСТВ

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

ДЕШИФРАТОРЫ

Краткие сведения из теории

Рис. 4

Дешифратор - логическая комбинационная схема, которая имеет n информационных входов и 2n выходов. Каждой комбинации логических уровней на входах будет соответствовать активный уровень на одном из выходов. Обычно n равно 2,3 или 4. На рис. 4 изображен дешифратор с n=3, активным уровнем является уровень логического нуля (в данной лабораторной работе для удобства вместо схемы дешифратора используется схема демультиплексора, это возможно благодаря сходству алгоритмов работы). На входы С, В, А можно подать следующие комбинации логических уровней: 000, 001, 010, ..., 111, всего 8 комбинаций.

Схема имеет 8 выходов, на одном из которых формируется низкий потенциал, на остальных - высокий. Номер этого единственного выхода, на котором формируется активный (нулевой) уровень, соответствует числу N, определяемому состоянием входов С, В, А следующим образом: N = С*2² + В*2¹ + А*2⁰.

Например, если на входы подана комбинация логических уровней 011, то из восьми выходов микросхемы (YO, Y1...Y7) на выходе с номером N=3 установится нулевой уровень сигнала (Y3=0), a все остальные выходы будут иметь уровень логической единицы. Этот принцип формирования выходного сигнала можно описать следующим образом:

(6)

Видно, что уровень сигнала на выходе Y3 описывается выражением: .

В таком же виде можно записать выражения для каждого выхода дешифратора:

, ,

, , (7)

, ,

, .

Рис.5

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

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

(8)

У дешифратора с несколькими входами управления функция разрешения, как правило, представляет собой логическое произведение всех разрешающих сигналов управления. Например, для дешифратора 74138 с одним прямым входом управления G1 и двумя инверсными G2A и G2B (рис. 5) функции выхода и разрешения G имеют вид:

(9)

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

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

2.2. Реализация произвольной функции с использованием дешифратора

Рассмотрим пример реализации функции трех аргументов с использованием базового дешифратора (рис.4). Функция задана аналитическим выражением .

Раскроем функцию до СДНФ, для этого последнее слагаемое умножим на 1, м запишем ее как

Функция не изменится, если взять от нее двойную инверсию

.

Используя теорему де Моргана (см. Приложение 2) раскроем внутреннюю инверсию

Анализируя выражения для выходов базового дешифратора (7) функцию можно записать

Теперь можно реализовать функцию используя базовый дешифратор, для этого нужно информацию с выходов Y0, Y3, Y4, Y7 подать на вход логического элемента 4-входового И-НЕ (рис.6).

Рис.6

2.3. Задание для выполнения

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

Вариант
1,21,41,61
2,22,42,62
3,23,43,63
4,24,44,64
5,25,45,65
6,26,46,66
7,27,47,67
8,28,48,68
9,29,49,69
10,30,50,70
11,31,51,71
12,32,52,72
13,33,53,73
14,34,54,74
15,35,55,75
16,36,56,76
17,37,57,77
18,38,58,78
19,39,59,79
20,40,60,80

МУЛЬТИПЛЕКСОРЫ

3.1. Краткие сведения из теории

Мультиплексор - комбинационная логическая схема, представляющая собой управляемый переключатель, который подключает к выходу один из информационных входов данных. Номер подключаемого входа равен числу (адресу), определяемому комбинацией логических уровней на входах управления. Кроме информационных и управляющих входов, схемы мультиплексоров содержат вход разрешения, при подаче на который активного уровня мультиплексор переходит в активное состояние. При подаче на вход разрешения пассивного уровня мультиплексор перейдет в пассивное состояние, для которого сигнал на выходе сохраняет постоянное значение независимо от значений информационных и управляющих сигналов. Число информационных входов у мультиплексоров обычно 2, 4, 8 или 16. На рисунке 7 представлен мультиплексор 8x1 с инверсным входом разрешения G, прямым Y и инверсным W-выходами ( ).

Рис. 7 – Мультиплексор 8x1

 

Уравнение работы мультиплексора

Функционирование мультиплексора, представленного на рисунке 2.1, описывается характеристическим уравнением, связывающим сигнал на выходе (Y) с разрешающим (G), входными информационными (D0 … D7) и управляющими (А, В, С) сигналами:

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

3.2. Реализация заданной функции с помощью мультиплексора

Логическая функция n переменных определена для 2n комбинаций значений переменных. Это позволяет реализовать функцию n - переменных на мультиплексоре, имеющем n - управляющих и 2n информационных входов. В этом случае каждой комбинации значений аргументов соответствует единственный информационный вход мультиплексора, на который подается значение функции.

Например, требуется реализовать функцию

Эта функция определена только для 8 комбинаций значений переменных, поэтому для её реализации можно использовать мультиплексор 8x1 с тремя управляющими входами. Составим таблицу истинности функции (табл.18):

Таблица 18
DN	c	b	a	F1
D0
D1
D2
D3
D4
D5
D6
D7

 

Из таблицы видно, что для реализации функции на мультиплексоре необходимо подать на информационный вход мультиплексора с номером N сигнал, значение которого равно соответствующему значению функции F1, т. е. на входы D0, D1, D5, D7 следует подать уровень логического нуля, а на остальные - уровень логической единицы. Таким образом, при подаче комбинации логических уровней на управляющие входы мультиплексора, к его выходу подключится вход, значение сигнала на котором равно соответствующему значению функции. Схемная реализация приведена на рисунке 8.

Рис. 8 – Схемная реализация

 

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

Составим таблицу истинности функции в зависимости от значений переменных а и b:

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

 

Таблица 19
N	b	A	F1
			с

Схемная реализация такого способа задания функции представлена на рисунке 9. Так как используются только два адресных входа, управляющий вход С можно заземлить. При этом состояние информационных входов D4...D7 безразлично. Уровень сигнала на выходе схемы определяется комбинацией уровней сигналов в точках А, В, С, соответствующих переменным а, b, с. Схема рисунка 9 по существу представляет собой мультиплексор 4x1 с двумя управляющими и четырьмя информационными входами.

Рисунок 9 – Схемная реализация второго способа задания функции

 

Если функцию можно представить в виде произведения одночлена на многочлен, то её также можно реализовать при помощи мультиплексора. Как следует из уравнения мультиплексора, сигнал, соответствующий одночлену, нужно подать на вход разрешения. Например, требуется реализовать функцию F2, описываемую следующим выражением:

.

При реализации данной функции на мультиплексоре сигнал, соответствующий переменной x, следует подать на его разрешающий вход. Рассмотрим, какие сигналы необходимо подать на управляющие входы мультиплексора. Выражение в скобках можно рассматривать как некоторую функцию f пяти переменных: а, b, с, d, е, из которых наиболее часто используются переменные a, b и с. Поэтому сигналы, соответствующие этим переменным, нужно подать на управляющие входы мультиплексора.

Определим, какие сигналы следует подать на информационные входы, чтобы реализовать функциюf. Для этого составим таблицу истинности функции в зависимости от значений переменных a, b и с.

 

Таблица 20
N	C	b	a	f
				d
				e
				d

 

Из таблицы видно, что на информационные входы с номерами N = 0, 2, 4, 6 нужно подать уровень логического нуля. Сигнал, соответствующий переменной d, нужно подать на входы с номерами N = 1, 5, сигнал, соответствующий переменной е, - на вход с номером 3. Соответствующая схемная реализация представлена на. рисунке 10.

Рис. 10 – Схемная реализация

Задание для выполнения

Разработать и собрать схему на основе мультиплексора 8x1, реализующую заданную логическую функцию Y. Варианты задач приведены ниже. Для выбора варианта взять 2 последние цифры в номере зачетной книжки.

Вариант
1,21,41,61
2,22,42,62
3,23,43,63
4,24,44,64
5,25,45,65
6,26,46,66
7,27,47,67
8,28,48,68
9,29,49,69
10,30,50,70
11,31,51,71
12,32,52,72
13,33,53,73
14,34,54,74
15,35,55,75
16,36,56,76
17,37,57,77
18,38,58,78
19,39,59,79
20,40,60,80

ТРИГГЕРЫ И СЧЕТЧИКИ

4.1. Краткие сведения из теории.

Триггеры

Основой последовательностных схем являются триггеры. Триггер имеет два устойчивых состояния: Q=l и Q=0, поэтому его иногда называют бистабильной схемой. В каком из этих состояний окажется триггер, зависит от сигналов на входах триггера и от его предыдущего состояния, т. е. он имеет память. Можно сказать, что триггер является элементарной ячейкой памяти.

Тип триггера определяется алгоритмом его работы. В зависимости от алгоритма работы, триггер может иметь установочные, информационные и управляющие входы. Установочные входы устанавливают состояние триггера независимо от состояния других входов. Входы управления раз­решают запись данных, подающихся на информационные входы. Наиболее распространенными являются триггеры RS, JK, D и Т-типов.

Триггер типа RS

RS-триггер - простейший автомат с памятью, который может находиться в двух состояниях. Триггер имеет два установочных входа: установки S (set - установка) и сброса R (reset - сброс), на которые подаются входные сигналы от внешних источников.

При подаче на вход установки активного логического уровня триггер устанавливается в 1 (Q = 1, = 0), при подаче активного уровня на вход сброса триггер устанавливается в 0 (Q = 0, = 1). Если подать на оба входа установки (возбуждения) пассивный уровень, то триггер будет сохранять предыдущее состояние выходов: Q=0 ( = 1) либо Q = l ( = 0). Каждое состояние устойчиво и поддерживается за счет действия обратных связей.

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

На рис. 11 и 12 показаны два вида RS-триггеров, выполненных на элементах ИЛИ-НЕ и И-НЕ.

Для схемы на рис. 11 активным уровнем является уровень логической единицы, для схемы на рис. 12 - уровень логического нуля. Схема на рис. 12 получила название RS-триггера с инверсными входами - RS-триггер.

Рис. 11

Рис. 12

RS-триггер является основным узлом для построения последовательностных схем. Название схем такого типа «последовательностные» означает, что состояние выхода зависит от того, в какой последовательности на входы подаются входные наборы и, каково было предшествующее внутреннее состояние. Так, если в RS-триггере (рис. 11) вначале установить комбинацию R=0, S=l (сокращенная запись - 01), а потом перейти к R=0, S=0 (00), то состояние выхода Q=l. Если же вначале устано­вить комбинацию 10, а потом перейти к 00, то состояние выхода будет другим - Q=0, несмотря на одинаковые комбинации сигналов на входах. Таким образом, при одном и том же входном наборе 00 выход триггера может находиться в разных состояниях.

Условия переходов триггеров из одного состояния в другое (алгоритм работы) можно описать табличным, аналитическим или графическим способами. Табличное описание работы RS-триггера (рис. 11) представлено в таблице истинности 21, описание работы RS-триггера с инверсными входами (рис. 12) в таблице 22.

Таблица 21.

R	S		Режим работы
			Хранение
			Установка «1»
			Установка «0»
		-	Запрещенное состояние

Таблица 22.

R	S		Режим работы
			Хранение
			Установка «1»
			Установка «0»
		-	Запрещенное состояние

В таблицах использованы следующие обозначения:

Q_t - предшествующее состояние выхода;

Q_t+1 - новое состояние, устанавливающееся после перехода (возможно Q_t+1 = Q_t);

“ – ”- неопределенное состояние.

Аналитическое описание (характеристическое уравнение) можно получить из таблицы 3.1 по правилам алгебры логики:

Синхронный RS-триггер

Условное обозначение синхронного RS-триггера приведено на рис. Триггер имеет дополнительно два логических элемента И-НЕ и синхронизирующий вход С, как показано на рис. 13.

Рис. 13

Таблица истинности синхронного RS-триггера приведена в таблице 23.

Таблица 23.

С	R	S		Режим работы
	х	х		Хранение
				Хранение
				Установка «1»
				Установка «0»
			-	Запрещенное состояние

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

JK-триггер

Триггер JK-типа имеет более сложную, по сравнению с RS-триггером, структуру и более широкие функциональные возможности. Помимо информационных входов J и К и прямого и инверсного выходов и , JK-триггер имеет вход управления С (этот вход также называют тактирующим или счетным), а также асинхронные установочные R и S-входы. Обычно активными уровнями установочных сигналов являются нули, как в схеме на рис. 14.2. Установочные входы имеют приоритет над остальными. Активный уровень сигнала на входе S устанавливает триггер в состояние Q = 1, а активный уровень сигнала на входе R - в состояние Q = 0, независимо от сигналов на остальных входах.

Если на входы установки одновременно подать пассивный уровень сигнала, то состояние триггера будет изменяться по фронту импульса на счетном входе в зависимости от состояния входов J и К, как показано в таблице истинности (табл. 24).

Таблица 24.

~R	~S	C	J	K		Режим работы
		´	´	´	-	Запрещенное состояние
		´	´	´		Асинхронная установка «0»
		´	´	´		Асинхронная установка «1»
			´	´		Хранение
						Хранение
						Установка «0»
						Установка «1»
						Переключение (противоположное состояние)

Работа JK-триггера описывается характеристическим уравнением:

Временные диаграммы его работы при R=S=1 приведены на рис. 14.

Рис. 14.

D-триггер

D-триггер имеет один информационный вход D (data - данные). Информация со входа D заносится в триггер по положительному перепаду импульса на счетном входе С и сохраняется до следующего положительного перепада на счетном входе триггера. Помимо счетного C и информационного D входов, триггер снабжён асинхронными установочными R и S входами. Установочные входы приоритетны.

Они устанавливают триггер независимо от сигналов на входах С и D. Функционирование D-триггера описывается таблицей истинности (табл. 25), и диаграммами входных и выходных сигналов (рис. 15).

Таблица 25.

~R	~S	C	D		Режим работы
		´	´	-	Запрещенное состояние
		´	´		Асинхронная установка «0»
		´	´		Асинхронная установка «1»
			´		Хранение
					Установка «0»
					Установка «1»

Рис. 15.

Характеристическое уравнение D-триггера:

.

Уравнение показывает, что состояние триггера на (t+1)-такте равно входному сигналу в момент, предшествующий тактовому перепаду сигнала С. Функциональная схема D-триггера может быть получена из схемы JK-триггера путем подключения входа К ко входу J через инвертор: D=J= .

Т-триггер (счетный триггер)

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

Рис.16

На рис. 16 представлены схемы организации Т-триггера на основе JK и D-триггеров. Счетный режим иллюстрируется временными диаграммами рис. 17.

Рис. 17

В JK-триггере с входами установки логическим нулем счетный режим реализуется путем подачи констант J=K=1 и R=S=1 и входного сигнала Т на вход С. В соответствии с таблицей функционирования при каждом отрицательном перепаде входного сигнала Т состояние триггера изменяет свое значение на противоположное.

В D-триггере счетный режим реализуется при помощи обратной связи (на вход D подается сигнал с инверсного выхода). Таким образом, всегда существует неравенство сигнала на входе D и сигнала на выходе Q: если Q=1, D=0. Следовательно, при каждом положительном перепаде сигнала на счетном входе С, в соответствии с принципом действия D-триггера состояние выхода будет изменяться на противоположное.

Таким образом, на каждые два входных тактовых импульса Т-триггер формирует один период выходного сигнала Q. Следовательно, триггер осуществляет деление частоты на ходе на 2:

,

где — частота следования импульсов на выходе триггера.

Счетчики

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

Изменение направления счета.

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

а) считывать выходные сигналы счетчика не с прямых, а с инверсных выходов триггеров.

Рис.18

Число, образуемое состоянием инверсных выходов триггеров счетчика, связано с числом,образованным состоянием прямых выходов триггеров следующим соотношением:

где n - разрядность выхода счетчика. В таблице 26 приведен пример связи числа на прямых выходах с числом на инверсных выходах триггеров счетчика.

Таблица 26