Построение кодопреобразователя

v010110v010111v011000v011001v101011v110110

• D₃ = 000100v000101v000110v000111v001000v001110v010001v010010v

v010011v010110v010111v100011v100101v100111v110001

• D₂ = 000011v000111v001000v001100v001101v001111v010001v010010v

v011000v011001v100000v100001v100010v100101v100111v110001v110110

• D₁ = 000001v000010v000101v000110v001000v001011v001101v010010v

V100001v100010v100111v101011v110001v110110

• D₀ = 000000v000010v000100v000110v001000v001010v001011v001110v

V001111v010010v010011v010111v011001v100000v100010v100101v110110

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

• Минимизирующие карты
• Одним из видов представления ФАЛ от небольшого числа переменных (как правило, не больше 5) являются диаграммы Карно или Вейча, которые строятся на развёртках многомерных кубов на плоскость. При этом вершины куба представляются клетками карты, координаты которых совпадают с координатами соответствующих вершин куба. Карта заполняется путём пометки кодов вершин, соответствующих наборам, на которых ФАЛ равна единице. Другими символами помечаются коды наборов, на которых ФАЛ не определена. Таким образом, диаграмма на карте Карно или Вейча соответствует представлению ФАЛ в СДНФ. Если строится карта Карно для нечётного количества переменных в наборе, то на расстоянии единицы слева от исходной карты для чётного количества переменных изображается повёрнутая на 180° вокруг оси, проходящей между исходной и новой картами, новая карта той же размерности. После этого в старшем разряде двоичных кодов наборов исходной карты добавляются незначащие нули, а в старшем разряде новой карты добавляются единицы. Эти две карты объединяются в одну большей размерности.
• Если строится карта Карно для чётного количества переменных в наборе, то на расстоянии единицы снизу от исходной карты для нечётного количества переменных изображается повёрнутая на 180° вокруг оси, проходящей между исходной и новой картами, новая карта той же размерности. После этого в старшем разряде двоичных кодов наборов исходной карты добавляются незначащие нули, а в старшем разряде новой карты добавляются единицы. Эти две карты объединяются в одну большей размерности.
• В картах наборы переменных, на которых функция принимает единичные значения, помечаются нечисловыми символами. Карта с нанесёнными на ней значениями ФАЛ называется диаграммой.
• Карты, на которых коды наборов изображаются в восьмеричной системе счисления, называются картами Вейча.
• Минимизация функций по методу Квайна
• При минимизации по методу Квайна в базисе И, ИЛИ, НЕ исходная ФАЛ задаётся в СДНФ Целью минимизации является нахождение всех первичных импликант и выбор некоторых из них для минимальной записи функции.

Импликанта функции - некоторая логическая функция, обращаемая в нуль при наборе переменных, на котором сама функция также равна нулю.

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

Первичная импликанта функции - импликанта типа элементарной конъюнкции некоторых переменных, никакая часть которой уже не является импликантой.

• Задача минимизации по методу Квайна решается путём попарного сравнения всех импликант, входящих в ФАЛ, с целью выявления возможности их неполного склеивания по какой-то переменной на промежуточных этапах. При склеивании снижается ранг термов. Склеивание проводится до тех пор, пока не останется ни одного терма, допускающего склеивание с каким-либо другим термом. Термы, подвергшиеся склеиванию, отмечаются. Неотмеченные термы представляют собой первичные импликанты. После получения множества всех первичных импликант исследуется возможность нахождения простейшей записи ФАЛ. Для этого составляется таблица, в первой строке которой записаны минтермы исходной ФАЛ, а в первом столбце записаны все найденные первичные импликанты. Клетки этой таблицы помечаются в том случае, если первичная импликанта входит в состав какого-либо минтерма исходной ФАЛ. После этого задача упрощения сводится к тому, чтобы найти такое минимальное количество первичных импликант, которые покрывают все столбцы минтермов исходной ФАЛ.
• Минимизация функций по методу Мак-Класки
• Недостатком метода Квайна является - необходимость исчерпывающего попарного сравнения или сопоставления всех минтермов на этапе нахождения первичных импликант. С ростом числа минтермов увеличивается количество попарных сравнений.
• Числовое представление ФАЛ позволяет упростить самый трудоёмкий первый этап. Все минтермы СДНФ ФАЛ записываются в виде их двоичных кодов, а все коды разбиваются по числу единиц на непересекающиеся группы.
• Минтермы, подлежащие склеиванию, различаются только по одной переменной, а их коды - только в одном разряде. По этой причине сравнению подлежат только двоичные коды минтермов соседних групп.
• Рассмотрев несколько методов минимизации ФАЛ, можно сделать вывод о том, что для решения нашей задачи наиболее подходящим является метод Мак-Класки.
• Минимизируем Y:

Y=010001v010010v010011v010100v010101v010110v010111v011000v011001v110001v110010v110011v110100v110101v110110v110111v111000v111001

• Склеивание 1

i	x Q4Q3Q2Q1Q0	Восьмеричное число
2	0100-1	21, 23
	010-01	21, 25
	01-001	21, 31
	-10001	21, 61
	01001-	22, 23
	010-10	22, 26
	-10010	22, 62
	01010-	24, 25
	0101-0	24, 26
	-10100	24, 64
	01100-	30, 31
	-11000	30, 70
3	010-11	23, 27
	-10011	23, 63
	0101-1	25, 27
	-10101	25, 65
	01011-	26, 27
	-010110	26, 66
	-11001	31, 71
	1100-1	61, 63
	110-01	61, 65
	11-001	61, 71
	11001-	62, 63
	110-10	62, 66
	11010-	64, 65
	1101-0	64, 65
	11100-	64, 66
4	-10111	27, 67
	110-11	63, 67
	1101-1	65, 67
	11011-	66, 67

Склеивание 2

i	x Q4Q3Q2Q1Q0	Восьмеричное число
2	010--1	21, 23, 25, 27
	-100-1	21, 23, 61, 63
	-10-01	21, 25, 61, 65
	-1-001	21, 31, 61, 71	A
	010-1-	22, 23, 26, 27
	-1001-	22, 23, 62, 63
	-10-10	22, 26, 62, 63
	0101--	24, 25, 26, 27
	-1010-	24, 25, 64, 65
	-101-0	24, 26, 64, 66
	-1100-	30, 70, 31, 71	B
3	-10-11	23, 27, 63, 67
	-101-1	25, 27, 65, 67
	-1011-	26, 27, 66, 67
	110--1	61, 63, 65, 67
	110-1-	62, 63, 66, 67
	1101--	64, 65, 66, 67

• Склеивание 3

i	x Q4Q3Q2Q1Q0	Восьмеричное число
2	-10--1	21, 23, 25, 27, 61, 63, 65, 67	C
	-10-1-	22, 23, 26, 27, 62, 63, 66, 67	D
	-101--	24, 25, 26, 27, 64, 65, 66, 67	E
	21	22	23	24	25	26	27	30	31	61	62	63	64	65	66	67	70	71
A
B
C
D
E

• Y= -1100-v-10-1-v-101--
• Минимизируем D₄
• D₄ = 001001v001010v001011v001100v001101v001110v001111v010100v
• v010110v010111v011000v011001v101011v110110

i	x Q4Q3Q2Q1Q0	Восьмеричное число
2	001001	11
	001010	12
	001100	14
	010100	24
	011000	30
3	001011	13
	001101	15
	001110	16
	010110	26
	011001	31
4	001111	17
	010111	27
	101011	53
	110110	67

• Склеивание 1

i	x Q4Q3Q2Q1Q0	Восьмеричное число
2	0010-1	11, 13
	001-01	11, 15
	0-1001	11, 31	A
	00101-	12, 13
	001-10	12, 16
	00110-	14, 15
	0011-0	14, 16
	0101-0	24, 26	B
	01100-	30, 31	C
3	001-11	13, 17
	-01011	13, 53	D
	0011-1	15, 17
	00111-	16, 17
	01011-	26, 27	E
	-10110	26, 67	F

• Склеивание 2

i	x Q4Q3Q2Q1Q0	Восьмеричное число
2	001--1	11, 13, 15, 17	G
	001-1-	12, 13, 16, 17	H
	0011--	14, 15, 16, 17	I

	11	12	13	14	15	16	17	24	26	27	30	31	53	67
A
B
C
D
E
F
G
H
I

• D₄ = 0101-0v01100-v-01011v01011-v-10110v001-1-v0011--
• Минимизируем D₃
• D₃ = 000100v000101v000110v000111v001000v001110v010001v010010v

v010011v010110v010111v100011v100101v100111v110001

i	x Q4Q3Q2Q1Q0	Восьмеричное число
1	000100	4
	001000	10	A
2	000101	5
	000110	6
	010001	21
	010010	22
3	000111	7
	001110	15
	010011	23
	010110	26
	100011	43
	100101	45
	110001	61
4	010111	27
	100111	47

• Склеивание 1

i	x Q4Q3Q2Q1Q0	Восьмеричное число
1	00010-	4, 5
	0001-0	4, 6
2	0001-1	5, 7
	-00101	5, 45
	00011-	6, 7
	00-110	6, 15	C
	0-0110	6, 26
	0100-1	21, 23	D
	-10001	21, 61	E
	01001-	22, 23
	010-10	22, 26
3	0-0111	7, 27
	-00111	7, 47
	010-11	23, 27
	01011-	26, 27
	100-11	43, 47	F
	1001-1	45, 47

• Склеивание 2

i	x Q4Q3Q2Q1Q0	Восьмеричное число
1	0001--	4, 5, 6, 7	G
2	-001-1	5, 7, 45, 47	H
	0-011-	6, 7, 26, 27	I
	010-1-	22, 23, 26, 27	J



	4	10	5	6	21	22	7	15	23	26	43	45	61	27	47
A
C
D
E
F
G
H
I
J

• D₃ = 001000v00-110v-10001v100-11v0001--v-001-1v010-1-
• Минимизируем D₂
• D₂ = 000011v000111v001000v001100v001101v001111v010001v010010v
• v011000v011001v100000v100001v100010v100101v100111v110001v110110

i	x Q4Q3Q2Q1Q0	Восьмеричное число
1	001000	10
	100000	40
2	000011	3
	001100	14
	010001	21
	010010	22	A
	011000	30
	100001	41
	100010	42
	100100	44
3	000111	7
	001101	15
	011001	31
	110001	61
4	001111	17
	100111	47
	110110	66	B

• Склеивание

i	x Q4Q3Q2Q1Q0	Восьмеричное число
1	001-00	10, 14	C
	0-1000	10, 30	D
	10000-	40, 41	E
	1000-0	40, 42	F
	100-00	40, 44	G
2	000-11	3, 7	H
	00110-	14, 15	I
	01-001	21, 31	J
	-10001	21, 61	K
	01100-	30, 30	L
	1-0001	41, 61	M
3	00-111	7, 17	N
	-00111	7, 41	O
	0011-1	15, 17	P



	3	7	10	14	15	17	21	22	30	31	40	41	42	44	47	61	66
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P

• D₂ = 010010v110110v1000-0v100-00v000-11v-00111
• Минимизируем D₁
• D₁ = 000001v000010v000101v000110v001000v001011v001101v010010v
• V100001v100010v100111v101011v110001v110110

i	x Q4Q3Q2Q1Q0	Восьмеричное число
1	000001	1
	000010	2
	001000	10	A
2	000101	5
	000110	6
	010010	22
	100001	41
	100010	42
3	001011	13
	001101	15
	110001	61
4	100111	47	B
	101011	53
	110110	66	C

Склеивание

i	x Q4Q3Q2Q1Q0	Восьмеричное число
1	000-01	1, 5	D
	-00001	1, 41	E
	000-10	2, 6	F
	0-0010	2, 22	G
	-00010	2, 42	H
2	00-101	5, 15	I
	1-0001	41, 61	J
3	-01011	13, 53	K

	1	2	5	6	10	13	15	22	41	42	47	53	61	66
A
B
C
D
E
F
G
H
I
J
K

• D₁ = 001000v100111v110110v000-10v0-0010v-00010v00-101v1-0001v-01011
• Минимизируем D₀
• D₀ = 000000v000010v000100v000110v001000v001010v001011v001110v
• V001111v010010v010011v010111v011001v100000v100010v100101v110110

i	x Q4Q3Q2Q1Q0	Восьмеричное число
0	000000	0
1	000010	2
	000100	4
	001000	10
	100000	40
2	000110	6
	001010	12
	010010	22
	100010	42
3	001011	13
	001110	16
	010011	23
	011001	31	A
	100101	45	B
4	001111	17
	010111	27
	110110	66	D

• Склеивание 1

i	x Q4Q3Q2Q1Q0	Восьмеричное число
0	0000-0	0, 2
	000-00	0, 4
	00-000	0, 10
	-00000	0, 40
1	00-010	2, 12
	0-0010	2, 22	E
	-00010	2, 42
	000-10	2, 6
	0001-0	4, 6
	0010-0	10, 12
	1000-0	40, 42
2	00101-	12, 13
	001-10	12, 16
	01001-	22, 23	F
	00-110	6, 16
3	001-11	13, 17
	00111-	16, 17
	010-11	23, 27	G

• Склеивание 2

i	x Q4Q3Q2Q1Q0	Восьмеричное число
0	000--0	0, 2, 4, 6	H
	00-0-0	0, 2, 10, 12	I
	-000-0	0, 2, 40, 42	J
1	00--10	2, 12, 6, 16	K
2	001-1-	12, 13, 16, 17	L



	0	2	4	6	10	12	13	16	17	22	23	27	31	40	42	45	66
A
B
D
E
F
G
H
I
J
K
L

• D₀ = 011001v100101v110110v010-11v000--0v00-0-0v-000-0v00--10v001-1-
• Заключение
• Для получения оптимального варианта кодирования необходимо сопоставлять результаты минимизации комбинационных схем при использовании всех возможных вариантов кодирования.
• Минимальный вариант построения принципиальной схемы может быть получен только после перебора и сравнения всех возможных вариантов построения цифрового устройства.
• Для практического использования методов минимизации исключительное значение имеет инженерная интуиция при выборе вариантов кодирования и минимизации. Функции выхода цифрового автомата нужно задавать сравнительно редко, поскольку чаще всего применяются цифровые автоматы, не имеющие выходной комбинационной схемы. Для более сложных цифровых автоматов входная комбинационная схема, как правило, представляет собой преобразователь кода, или шифратор, состояния блок памяти цифрового автомата в выходной код цифрового автомата. Для большинства стандартных применений выходные комбинационные схемы цифровых автоматов минимизированы, разработаны и производятся в виде интегральных схем.
• Таким образом, цель минимизации выходной комбинационной цифрового автомата зачастую сводится к выбору интегральных микросхем для конкретного использования.
• Для структурного синтеза цифровых автоматов желательно применять табличные методы, так как они выполняются в более строгой форме, чем структурный синтез по графу, который требует огромного внимания на процессах синтеза и проверки его результатов. Количество ошибок при применении метода структурного синтеза по графу намного больше количества ошибок при использовании табличного метода структурного синтеза при всех прочих одинаковых условиях выполнения процесса синтеза.
• В ходе выполнения курсовой работы было произведено построение кодопреобразователя по заданным входным и выходным функциям.
• В процессе выполнения работы нами были приобретены практические навыки по курсам « Дискретная математика» и «Цифровые автоматы».

Литература

• 1. Гудилин А.В. Цифровая схемотехника. Челябинск, 2000.
• 2. Иванов В.И. Синтез цифровых автоматов для систем связи и управления. Челябинск, 1980
• 3. Щелкунов Н.Н., Дианов А.П. Процедуры программирования логических матриц, - Микропроцессорные средства и системы, 1986, №2.
• 4. Иванов В.И. Синтез цифровых автоматов для систем связи и управления, Челябинск, ЧПИ, 1980.
• 5. Баранов СИ. Синтез микропрограммных автоматов. - Л.: Энергия, 1979.
• 6. Электронный конспект лекций Гудилин Алексей Евгеньевич.
• 7. Конспект лекций по курсу цифровые автоматы. ЮУрГУ 2004.