Синтез логических устройств в заданном базисе

 

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

 

 

Рисунок 4 – Пример логической схемы устройства

 

Пример – Заданную функцию f перевести в базисы И-НЕ и ИЛИ-НЕ. Исходная ДНФ в базисе И-НЕ имеет вид:

 

.

 

Аналогично КНФ в базисе ИЛИ-НЕ имеет вид:

 

.

 

Пример – Пусть логическая функция задана выражением

 

.

 

Привести логическую функцию в базис И-НЕ, ИЛИ-НЕ:

а) приводим функцию к базису И-НЕ:

 

 

;

 

;

 

;

 

;

 

б) приводим функцию к базису ИЛИ-НЕ:

 

;

 

;

 

;

 

;

 

.

 

 

5.3 Задания для самостоятельной работы

 

1 Дешифратор управляет семисегментным (сегменты a, b, c, d, e, f, g) индикатором, отображающим символы от 0 до 9, a, b, c, d, E, F (рисунки 5–6).

 

 

Рисунок 5 – Стандартное обозначение сегментов индикатора

 

 

 

Рисунок 6 – Символы, отображаемые индикатором

 

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

 

Таблица 1 – Варианты синтеза логической схемы управления

 

Базис	Сегмент индикатора
	a	b	c	d	e	f	g
И-НЕ	1	3	5	7	9	11	13
ИЛИ-НЕ	2	4	6	8	10	12	14

 

2 Синтезировать в базисе И-НЕ (ИЛИ-НЕ) схему для поразрядного сравнения двух двоичных четырехразрядных чисел и выдачи результатов этого сравнения. Для каждой пары сравниваемых разрядов a[n] и b[n] вычисляется сумма по модулю 2 (таблица 2).

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

 

 

Таблица 2 – Поразрядное вычисление суммы по модулю 2

 

a[n]	b[n]	a[n] b[n]	a[n]	b[n]	a[n] b[n]
0	0	0	1	0	1
0	1	1	1	1	0

 

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

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

 

Таблица 3 – Преобразование двоичного кода в код Грея

 

Двоичный код (входы)			Код Грея (выходы)
C(22)	B(21)	A(20)	P1	P2	P3
0	0	0	0	0	0
0	0	1	0	0	1
0	1	0	0	1	1
0	1	1	0	1	0
1	0	0	1	1	0
1	0	1	1	1	1
1	1	0	1	0	1
1	1	1	1	0	0

 

5 Синтезировать в базисе И-НЕ (ИЛИ-НЕ) сумматор для выполнения операции сложения четырехразрядных чисел в двоичном коде. Сложение двух двоичных чисел производится в соответствии с таблицей истинности (таблица 4), где A_i и B_i – значения складываемых двоичных чисел в данном разряде; S_i – результат суммирования в данном разряде; P_i, P_i–1 – значения сигналов переноса соответственно в данном и предыдущем разряде.

 

Таблица 4 – Выполнение операции сложения двоичных чисел

 

Вход			Выход
Ai	Bi	Pi–1	Pi	Si
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

 

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

 

Таблица 5 – Преобразование двухразрядного кода в трехразрядный

 

Вход		Выход
a1	a0	b2	b1	b0
0	0	0	0	0
0	1	1	0	1
1	0	0	0	1
1	1	1	1	0

 

7 Реализовать функции И, ИЛИ и НЕ на логических элементах в базисе И-НЕ (ИЛИ-НЕ).

8 Синтезировать в базисе И-НЕ (ИЛИ-НЕ) устройства, заданные логической функцией:

1) ;

2) ;

3) ;

4) ;

5) ;

6) ;

7) ;

8) ;

9) ;

10) ;

11) ;

12) ;

13) ;

14) ;

15) ;

16) ;

17) ;

18) ;

19) ;

20) ;

21) ;

22) ;

23) ;

24) ;

25) .

 

6 Способы задания абстрактного конечного автомата

 

6.1 Понятие конечного автомата

 

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

По входному каналу в каждый момент времени t = 1, 2,... в устройство М поступают входные сигналы (из некоторого конечного множества сигналов). Задается закон изменения состояния к следующему моменту времени в зависимости от входного сигнала и состояния устройства в текущий момент времени. Выходной сигнал зависит от состояния и входного сигнала в текущий момент времени (рисунок 7).

 

 

Рисунок 7 – Абстрактный конечный автомат

 

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

Конечным автоматом называется структура , где X, Q, Y – произвольные непустые конечные множества.

Множество  называется входным алфавитом, а его элементы – входными символами, их последовательности – входными словами. Множество  называется множеством состояний, а его элементы – состояниями. Множество  называется выходным алфавитом, а его элементы – выходными символами, их последовательности – выходными словами.

Функция  называется функцией переходов. Функция  называется функцией выходов, т. е. .

Если в момент времени t = 1, 2,... на вход автомата А = (X; Q; Y; δ; λ ) последовательно подаются входные символы  и при этом автомат находится в состоянии , то под воздействием символа x(t)автомат перейдет в новое состояние  и выдаст выходной сигнал y(t).

Величины x(t), y(t), q(t), q(t+1) связаны между собой следующими уравнениями:

 

 

Эти уравнения называются каноническими уравнениями автомата А.

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

 

6.2 Способы задания конечного автомата

 

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

Табличное задание автомата. Из определения автомата следует, что его всегда можно задать таблицей с двумя входами, содержащей m строк и n столбцов, где на пересечении столбца q и строки a стоят значения функций ,  (таблица 6).

 

Таблица 6 – Табличное задание автомата

 

a	q
	q1	…	qj	…	qn
a1	;	…	;	…	;
…	…	…	…	…	…
ai	;	…	;	…	;
…	…	…	…	…	…
am	;	…	;	…	;

 

Задание автомата диаграммой Мура. Другой способ задания конечного автомата – графический. При этом способе состояния автомата изображают кружками, в которые вписывают символы состояний q_j (j = 1, ..., n). Из каждого кружка проводится т стрелок (ориентированных ребер), взаимно-однозначно соответствующих символам входного алфавита .Стрелке, соответствующей символу  и выходящей из кружка , приписывается пара ( ), причем эта стрелка ведет в кружок, соответствующий .

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

 

Примеры конечных автоматов

 

Приведем несколько примеров конечных автоматов.

Пример 1. Элемент задержки (элемент памяти).

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

 

 

Рисунок 8 – Элемент задержки

 

Предположим, что входной и, следовательно, выходной алфавиты есть X = {0, 1}; Y = {0, 1}. Тогда Q = {0, 1}. Под состоянием элемента задержки в момент времени t понимается содержание элемента памяти в данный момент. Таким образом, q(t) = x(t – 1), a y(t) = q(t) = x(t – 1).

Зададим элемент задержки таблицей 8, где а₁= 0, а₂ = 1, q₁= 0, q₂= 1,

 

; ;

 

; ;

 

; ;

 

; .

 

Таблица 8 – Автоматная таблица элемента задержки

 

a	q
	0	1
0	δ = 0;   λ = 0	δ = 0;  λ = 1
1	δ = 1;   λ = 0	δ = 1;  λ = 1

 

Диаграмма Мура изображена на рисунке 9.

 

 

Рисунок 9 – Диаграмма Мура элемента задержки

 

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

Обратим внимание на то, что т = п = р = 2. Тогда k = r = s = l, и поэтому элемент задержки задается функциями δ и λ. Таблица истинности этих функций содержит 2^{k + r} = 2² = 4 строки и k + r + r + s = 4 столбца.

 

Таблица 9 – Значения функций δ и λ элемента задержки

 

x	z	δ	λ
0	0	0	0
0	1	0	1
1	0	1	0
1	1	1	1

 

Пример 2 – Схема сравнения на равенство.

Схема сравнения на равенство представляет собой устройство, сравнивающее числа x₁и х₂, заданные в двоичной системе исчисления. Это устройство работает следующим образом. На вход устройства поступают по двум каналам числа x₁и х₂. Число x₁является результатом сложения по модулю 2 байта данных, хранящегося в памяти компьютера. Число x₂является битом паритета, дополняющего число x₁ так, чтобы их сумма сложения по модулю 2 была равна нулю. Это достигается при равенстве x₁и х₂. Поэтому эти числа сравниваются устройством сравнения. При совпадении разрядов на выходе схемы формируется выходной сигнал 0, в противном случае на выходе появляется сигнал 1, что говорит о сбое в памяти. Ясно, что появление 1 в выходной последовательности означает, что сравниваемые числа x₁и х₂различны. Если же выходная последовательность является нулевой, то x₁ = х₂.

Для этого автомата X = {00; 01; 10; 11}; Y = {0, 1}.

Функционирование схемы определяется двумя состояниями. Состояние q₀ соответствует равенству сравниваемых в данный момент разрядов. При этом автомат остается в этом же состоянии. Если в следующий момент сравниваемые разряды будут различны, то автомат перейдет в новое состояние q₁и в нем остается. Так как это означает, что числа различны.

Таким образом, схему сравнения можно задать таблицей 10.

 

Таблица 10 – Автоматная таблица схемы сравнения

 

x	q
	q0	q1
00	q0;  0	q0;  1
01	q1;  1	q1;  1
10	q1;  1	q1;  1
11	q0;  0	q0;  1

 

Диаграмма Мура схемы сравнения на равенство изображена на рисунке 10.

 

 

Рисунок 10 – Диаграмма Мура схемы сравнения на равенство

 

6.4 Задания для самостоятельной работы

 

Задание 1

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

 

1	x	q				4	x	q
		0	1	2	3			0	1	2	3
	0	(1; 1)	(3; 0)	(2; 0)	(2; 0)		0	(1; 0)	(3; 1)	(2; 0)	(1; 0)
	1	(2; 1)	(2; 0)	(3; 0)	(3; 0)		1	(3; 0)	(1; 1)	(0; 1)	(3; 1)

 

2	x	q				5	x	q
		0	1	2	3			0	1	2	3
	0	(0; 0)	(1; 1)	(3; 1)	(2; 0)		0	(2; 0)	(0; 0)	(3; 1)	(1; 0)
	1	(2; 0)	(0; 1)	(3; 1)	(1; 0)		1	(1; 0)	(0; 0)	(0; 0)	(3; 0)

 

3	x	q				6	x	q
		0	1	2	3			0	1	2	3
	0	(3; 0)	(2; 0)	(1; 1)	(0; 1)		0	(2; 1)	(2; 1)	(2; 1)	(2; 1)
	1	(0; 1)	(1; 1)	(2; 0)	(3; 0)		1	(1; 1)	(3; 1)	(0; 0)	(1; 0)

 

7	x	q				14	x	q
		0	1	2	3			0	1	2	3
	0	(1; 0)	(2; 0)	(2; 1)	(3; 0)		0	(0; 1)	(1; 1)	(2; 1)	(3; 1)
	1	(3; 0)	(3; 1)	(2; 1)	(1; 0)		1	(0; 0)	(0; 1)	(3; 1)	(2; 1)

 

8	x	q				15	x	q
		0	1	2	3			0	1	2	3
	0	(0; 0)	(1; 1)	(2; 0)	(3; 1)		0	(0; 0)	(0; 1)	(2; 0)	(2; 1)
	1	(1; 0)	(0; 1)	(3; 0)	(2; 1)		1	(1; 0)	(1; 1)	(3; 0)	(3; 1)

 

9	x	q				16	x	q
		0	1	2	3			0	1	2	3
	0	(1; 1)	(0; 0)	(3; 1)	(2; 0)		0	(0; 1)	(0; 0)	(1; 0)	(1; 0)
	1	(0; 1)	(2; 0)	(2; 1)	(3; 0)		1	(2; 0)	(2; 1)	(3; 0)	(3; 1)

 

10	x	q				17	x	q
		0	1	2	3			0	1	2	3
	0	(0; 0)	(1; 1)	(2; 1)	(3; 1)		0	(1; 0)	(3; 1)	(2; 1)	(2; 1)
	1	(3; 1)	(0; 1)	(1; 1)	(2; 0)		1	(2; 1)	(2; 0)	(3; 0)	(3; 0)

 

11	x	q		18	x	q
		0	1			0	1
	0	(0; 0)	(0; 1)		0	(0; 0)	(1; 1)
	1	(0; 1)	(1; 0)		1	(1; 1)	(1; 1)
	2	(0; 1)	(1; 0)		2	(1; 1)	(1; 1)
	3	(1; 0)	(1; 1)		3	(0; 0)	(1; 1)

 

12	x	q		19	x	q
		0	1			0	1
	0	(0; 0)	(1; 1)		0	(0; 0)	(1; 1)
	1	(1; 0)	(1; 1)		1	(0; 0)	(0; 1)
	2	(0; 1)	(0; 0)		2	(1; 1)	(1; 1)
	3	(–; 1)	(–; 0)		3	(1; 1)	(0; 1)

 

13	x	q			20	x	q
		1	2	3			1	2	3
	0	(2; 0)	(2; 1)	(3; 1)		0	(1; 0)	(2; 1)	(0; 2)
	1	(1; 1)	(3; 0)	(3; 1)		1	(2; 1)	(2; 1)	(3; 0)
	2	(1; 1)	(2; 1)	(1; 0)		2	(3; 2)	(0; 1)	(2; 0)

 

Задание 2

Для автомата, заданного диаграммой Мура, выпишите соответствующую таблицу и систему булевых функций (рисунки 11–26).

 

 

Рисунок 11

Рисунок 12

 

 

 

Рисунок 13

Рисунок 14

 

 

 

Рисунок 15

Рисунок 16

 

Рисунок 17

Рисунок 18

 

 

Рисунок 19

Рисунок 20

 

 

Рисунок 21

Рисунок 22

 

 

Рисунок 23

Рисунок 24

 

 

Рисунок 25

Рисунок 26

 

 

Требования к контрольной работе

 

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

Образец с заданиями по АКР:

Задание 1. Для данного множества А построить множество всех подмножеств, т. е. булеан множества .

Задание 2. Определить, является ли отношение R, заданное на множестве  рефлексивным, симметричным, антирефлексивным, антисимметричным. Построить граф и матрицу отношения .

Задание 3. Синтезировать в базисе ИЛИ-НЕ устройство, заданное логической функцией: .

Задание 4. Даны графы G₁ и G₂. Найдите , . Найдите матрицы смежности, инцидентности:

Задание 5. Для автомата, заданного диаграммой Мура, выпишите соответствующую таблицу.

 

Список литературы

 

1 Новиков, Ф. А. Дискретная математика для программистов: Учебник / Ф. А. Новиков. ‑ 2-е изд. ‑ СПб.: Питер, 2006. – 364 с.

2 Вороненко, А. А. Дискретная математика. Задачи и упражнения с решениями: Учебно-методическое пособие / А.А. Вороненко. – М.: ООО " Научно-издательский центр ИНФРА-М", 2014. – 104 с.

3 Поздняков, С. Н. Дискретная математика: учебник для вузов / С. Н. Поздняков, С. В. Рыбин. ‑ М.: Академия, 2008. – 448 с.

4 Хопкрофт, Дж. Введение в теорию автоматов, языков и вычислений: [пер. с англ.] / Дж. Хопкрофт, Р. Мотвани, Дж. Ульман. – 2-е изд. – М.: Вильямс, 2008. – 528с.

5 Шевелев, Ю. П. Дискретная математика: учеб. пособие для вузов / Ю. П. Шевелев. – СПб.: Лань, 2008. – 592 с.

6 Окулов С. М. Дискретная математика. Теория и практика решения задач по информатике: учеб. пособие / С. М. Окулов. – М.: Бином, 2008. – 422 с.

7 Шапорев С. Д. Дискретная математика. Курс лекций по практическим занятиям: Курс лекций по практическим занятиям для вузов / С. Д. Шапорев. ‑ СПб.: БХВ-Петербург, 2007. – 400 с.

8 Певзнер, Л. Д. практикум по математическим основам теории систем: учеб. Пособие / Л. Д. Певзнер. СПб.; М.; Краснодар: Лань, 2013. – 400 с.

9 Галушкина, Ю. И. Конспект лекций по дискретной математике / Ю. И. Галушкина, А. Н. Марьямов. – М.: Айрис-Пресс, 2007. – 176 с.

10 Трохимчук, Р. М. Основы дискретной математики. Практикум / Р. М. Трохимчук. – Киев: МАУП, 2004. – 168 с.

11 Прикладная теория цифровых автоматов / К. Г. Самофалов [и др.]. – Киев: Вища шк., Головное изд-во, 1987. – 375 с.

 

⇐ Предыдущая123

Поделиться: