Построение кодопреобразователя
Задачей этапа структурного синтеза является построение принципиальной схемы автомата из элементарных автоматов заданного типа. Элементарные автоматы подразделяются на два больших класса:
элементарные автоматы памяти (запоминающие элементы);
элементарные автоматы без памяти (элементарные комбинационные схемы или логические элементы).
Задача синтеза цифрового автомата имеет решение в том случае, если система элементарных автоматов является структурно полной.
Всякая система элементарных автоматов, содержащая элементарный автомат, Мура (триггер) и какую-нибудь функционально полную систему логических элементов является структурно полной системой.
Если автомат имеет М состояний, то для двоичного структурного алфавита количество триггеров в блоке памяти этого автомата
n=]log2M[ (1)
где ]...[- ближайшее большее целое число.
Если в каждую клетку таблицы переходов и выходов записать двоичный код, соответствующий размещённым там состояниям или выходным сигналам цифрового автомата, то таким образом получаются кодированные таблицы переходов и выходов.
Кодированная таблица выходов является табличным описанием системы булевых функций, реализуемых схемой КСВЫХ. Кодированная таблица переходов только после переработки с использованием матрицы переходов для заданного типа триггеров будет называться кодированной таблицей возбуждений и соответствовать описанию комбинационной схемы КСВХ.
Таким образом, задача синтеза состоит в определении по таблицам функций выхода и функций возбуждения триггеров заданного типа в блоке памяти, минимизации их для выбранной элементной базы и схемной реализации в функционально полном базисе элементов.
Выбор триггера
Комбинационная схема с обратными связями, имеющая два устойчивых состояния и предназначенная для хранения одного бита информации, называется элементарным автоматом или триггером.
Для синтеза цифровых автоматов триггеры рассматриваются как элементы систем, и важным является изучение его поведения в системе, а не внутренняя структура или принципиальная схема. В этом состоит системотехнический подход к изучению триггеров различных типов.
Триггер типа RS. Название триггера происходит от английских слов set и reset, он имеет два входа - S для установки триггера в единицу и R для установки его в ноль. Как правило, он имеет два выхода: прямой и инверсный. Если для перевода триггера из одного состояния в другое на установочные входы необходимо подавать не логические единица, а нули, то такой триггер называется триггером с инверсным управлением.

Рис. 2. Триггеры типа RS с прямым (а) и инверсным (б) управлением
Триггер типа JK. Триггер типа JK работает также как и триггер RS, с той лишь разницей, что допустима одновременная подача сигналов J=K=1, которая изменяет его состояние на обратное. Вход K эквивалентен входу R, а вход J - входу S.
Триггер типа D. Название триггера происходит от английского слова «задержка» (delay). Триггер имеет один вход. На выходе он должен повторять сигнал, существовавший на своем входе в предыдущий такт: D-триггеры всегда выпускаются синхронными, так как асинхронный триггер работает просто как повторитель входных сигналов.

Рис. 3. Условные обозначения JK и D триггера.
Триггер типа T. триггеры этого типа выпускаются промышленностью как самостоятельные устройства. Они могут быть собраны из триггеров других типов как на рис. 4. логическая единица, приложенная к T-входу триггера, меняет его состояние на обратное.

Рис. 4. Счетные триггеры
Триггер типа RST. Это счетный триггер с двумя установочными входами. Многовходовый триггер в цифровом автомате позволяет упростить его структуру.
Для решения нашей задачи выберем D-триггер, который имеет всего один вход (D) и на выходе он повторяет сигнал на входе D, существовавший в предыдущем такте автоматного времени.
Поскольку в пределах периода синхроимпульсов входной сигнал появляется в произвольный момент времени, то на выход входной сигнал проходит с произвольной задержкой, не превышающей длительность периода синхросигнала.
Представление функции возбуждения
По формуле (1) рассчитаем необходимое количество разрядов для кодирования: N = ]log223[ = 5 разрядов.
Если в каждую клетку таблицы переходов и выходов записать двоичный код, соответствующий размещённым там состояниям или выходным сигналам цифрового автомата, то таким образом получаются кодированные таблицы переходов и выходов.
Кодированная таблица выходов является табличным описанием системы булевых функций, реализуемых схемой КСвых. Кодированная таблица переходов только после переработки с использованием матрицы переходов для заданного типа триггеров будет называться кодированной таблицей возбуждений и соответствовать описанию комбинационной схемы КСВХ. Очевидно, что при кодировании переходов и выходов можно придерживаться двух принципов описания булевых функций. Если желательно получить табличное описание функций выходов с наименьшим количеством единичных значений, то для кодирования часто встречающихся в таблице выходов сигналов следует использовать коды с максимально возможным количеством нулей в коде, а для кодирования следующих по количеству ссылок в таблице выходов сигналов использовать коды с увеличивающимся количеством единиц в кодовых комбинациях. Для кодирования состояний блока памяти на D триггерах также можно использовать этот принцип кодирования, поскольку таблица возбуждений для них совпадает с таблицей переходов. Рекомендовать этот принцип для, всеобщего применения при синтезе автоматов нельзя, так как при минимизации булевых функций возможно получение более простых результирующих форм представления функций, имеющих более сложную запись в СДНФ (Нормальная дизьюктивная форма - это набор переменных без общих отрицаний и скобок. Совершенная НДФ - это когда все наборы переменных имею одинаковую длину. СДНФ - это набор конъюнкций переменных одинаковой длины). Этот принцип можно использовать только в том случае, если ФАЛ выходов и ФАЛ возбуждений для D триггеров не подлежат минимизации, поскольку реализуются на мультиплексорах, дешифраторах или постоянных запоминающих устройствах.
Второй принцип кодирования соответствует противоположному подходу и ориентирован на возможность получения значительных упрощений ФАЛ в результате минимизации. Для кодирования выходных сигналов с максимальным количеством ссылок в таблице выходов используется код с максимальным количеством единиц, а для кодирования следующих по количеству ссылок в таблице выходных сигналов использовать коды с уменьшающимся количеством единиц в кодовых комбинациях. Этот принцип также без оговорок применим для кодирования состояний блока памяти на D триггерах для случая применения элементной базы, требующей минимизации для своей реализации. Минимальный по материальным затратам вариант кодирования выбирается из конечных результатов при использовании всевозможных вариантов кодирования.
Таблица состояний и выходов нормализованного автомата
|
Вх/сост |
G1 |
G2 |
G3 |
G4 |
G5 |
G6 |
G7 |
G8 |
G9 |
G10 |
G11 |
G12 |
G13 |
| 0 |
G2/0 |
G3/0 |
G4/0 |
G5/0 |
G10/0 |
G11/0 |
G12/0 |
G13/0 |
G16/0 |
G17/0 |
G18/0 |
G20/0 |
G21/0 |
| 1 |
G6/0 |
G7/0 |
G8/0 |
G9/0 |
-/- |
G14/0 |
-/- |
G15/0 |
-/- | -/- | -/- |
G19/0 |
-/- |
|
Вх/сост |
G14 |
G15 |
G16 |
G17 |
G18 |
G19 |
G20 |
G21 |
G23 |
G24 |
G25 |
G26 |
|
| 0 |
G23/0 |
G26/0 |
G22/0 |
G1/0 |
G13/0 |
G16/0 |
G10/1 |
G17/1 |
G25/1 |
G26/1 |
G21/0 |
G22/1 |
|
| 1 | -/- | -/- |
-/- |
-/- |
G15/1 |
-/- |
-/- |
-/- |
G24/1 |
-/- |
-/- |
-/- |
Закодируем состояния тремя разрядами:
| Состояние/код | Q4Q3Q2Q1Q0 |
| G1 | 00000 |
| G2 | 00001 |
| G3 | 00010 |
| G4 | 00011 |
| G5 | 00100 |
| G6 | 00101 |
| G7 | 00110 |
| G8 | 00111 |
| G9 | 01000 |
| G10 | 01001 |
| G11 | 01010 |
| G12 | 01011 |
| G13 | 01100 |
| G14 | 01101 |
| G15 | 01110 |
| G16 | 01111 |
| G17 | 10000 |
| G18 | 10001 |
| G19 | 10010 |
| G20 | 10011 |
| G21 | 10100 |
| G22 | 10101 |
| G23 | 10110 |
| G24 | 10111 |
| G25 | 11000 |
| G26 | 11001 |
| Q Q* | D |
| 0 0 | 0 |
| 0 1 | 1 |
| 1 0 | 2 |
| 1 1 | 1 |
Таблица переходов D-триггера:
Для случая D-триггера кодированная таблица возбуждения блока памяти совпадает с кодированной таблицей переходов:
| Состояние/код | Q4Q3Q2Q1Q0 | 0 | 1 |
| D4D3D2D1D0 | D4D3D2D1D0 | ||
| G1 | 00000 | 00001 | 00101 |
| G2 | 00001 | 00010 | 00110 |
| G3 | 00010 | 00011 | 00111 |
| G4 | 00011 | 00100 | 01000 |
| G5 | 00100 | 01001 | 00000 |
| G6 | 00101 | 01010 | 01101 |
| G7 | 00110 | 01011 | 00000 |
| G8 | 00111 | 01100 | 01110 |
| G9 | 01000 | 01111 | 00000 |
| G10 | 01001 | 10000 | 00000 |
| G11 | 01010 | 10001 | 00000 |
| G12 | 01011 | 10011 | 10010 |
| G13 | 01100 | 10100 | 00000 |
| G14 | 01101 | 10110 | 00000 |
| G15 | 01110 | 11001 | 00000 |
| G16 | 01111 | 10101 | 00000 |
| G17 | 10000 | 00000 | 00000 |
| G18 | 10001 | 01100 | 01110 |
| G19 | 10010 | 01111 | 00000 |
| G20 | 10011 | 01001 | 00000 |
| G21 | 10100 | 10000 | 00000 |
| G22 | 10101 | 00000 | 00000 |
| G23 | 10110 | 11000 | 10111 |
| G24 | 10111 | 11001 | 00000 |
| G25 | 11000 | 10100 | 00000 |
| G26 | 11001 | 10101 | 00000 |
Выполним конкатенацию кодов входных сигналов и кодов состояний по порядку следования переменных xQ2Q1Q0 и заполним таблицу истинности для функций выхода и возбуждений.
Таблица истинности функций выходов и входов:
|
XQ4Q3Q2Q1Q0 |
D4D3D2D1D0 |
Y |
| 000000 | 00001 | 0 |
| 000001 | 00010 | 0 |
| 000010 | 00011 | 0 |
| 000011 | 00100 | 0 |
| 000100 | 01001 | 0 |
| 000101 | 01010 | 0 |
| 000110 | 01011 | 0 |
| 000111 | 01100 | 0 |
| 001000 | 01111 | 0 |
| 001001 | 10000 | 0 |
| 001010 | 10001 | 0 |
| 001011 | 10011 | 0 |
| 001100 | 10100 | 0 |
| 001101 | 10110 | 0 |
| 001110 | 11001 | 0 |
| 001111 | 10101 | 0 |
| 010000 | 00000 | 0 |
| 010001 | 01100 | 1 |
| 010010 | 01111 | 1 |
| 010011 | 01001 | 1 |
| 010100 | 10000 | 1 |
| 010101 | 00000 | 1 |
| 010110 | 11000 | 1 |
| 010111 | 11001 | 1 |
| 011000 | 10100 | 1 |
| 011001 | 10101 | 1 |
| 100000 | 00101 | 0 |
| 100001 | 00110 | 0 |
| 100010 | 00111 | 0 |
| 100011 | 01000 | 0 |
| 100100 | 00000 | 0 |
| 100101 | 01101 | 0 |
| 100110 | 00000 | 0 |
| 100111 | 01110 | 0 |
| 101000 | 00000 | 0 |
| 101001 | 00000 | 0 |
| 101010 | 00000 | 0 |
| 101011 | 10010 | 0 |
| 101100 | 00000 | 0 |
| 101101 | 00000 | 0 |
| 101110 | 00000 | 0 |
| 101111 | 00000 | 0 |
| 110000 | 00000 | 0 |
| 110001 | 01110 | 1 |
| 110010 | 00000 | 1 |
| 110011 | 00000 | 1 |
| 110100 | 00000 | 1 |
| 110101 | 00000 | 1 |
| 110110 | 10111 | 1 |
| 1101111 | 00000 | 1 |
| 111000 | 00000 | 1 |
| 111001 | 00000 | 1 |
Поскольку
числовая СДНФ
форма ФАЛ имеет
самую компактную
запись и позволяет
при необходимости
перейти к любому
другому описанию
этой функции,
по таблице
истинности
функций выходов
и входов запишем
именно в числовой
форме функции
выходов Y,
D1, D2,
D3, D4,
D5 от
x Q4Q3Q2Q1Q0.
Y = 010001v010010v010011v010100v010101v010110v010111v011000v011001v
v110001v110010v110011v110100v110101v110110v110111v111000v111001
D4 = 001001v001010v001011v001100v001101v001110v001111v010100v
v010110v010111v011000v011001v101011v110110
D3 = 000100v000101v000110v000111v001000v001110v010001v010010v
v010011v010110v010111v100011v100101v100111v110001
D2 = 000011v000111v001000v001100v001101v001111v010001v010010v
v011000v011001v100000v100001v100010v100101v100111v110001v110110
D1 = 000001v000010v000101v000110v001000v001011v001101v010010v
V100001v100010v100111v101011v110001v110110
D0 = 000000v000010v000100v000110v001000v001010v001011v001110v
V001111v010010v010011v010111v011001v100000v100010v100101v110110
Для дальнейшей работы необходимо минимизировать полученные выходные функции автомата.
Минимизирующие карты
Одним из видов представления ФАЛ от небольшого числа переменных (как правило, не больше 5) являются диаграммы Карно или Вейча, которые строятся на развёртках многомерных кубов на плоскость. При этом вершины куба представляются клетками карты, координаты которых совпадают с координатами соответствующих вершин куба. Карта заполняется путём пометки кодов вершин, соответствующих наборам, на которых ФАЛ равна единице. Другими символами помечаются коды наборов, на которых ФАЛ не определена. Таким образом, диаграмма на карте Карно или Вейча соответствует представлению ФАЛ в СДНФ. Если строится карта Карно для нечётного количества переменных в наборе, то на расстоянии единицы слева от исходной карты для чётного количества переменных изображается повёрнутая на 180° вокруг оси, проходящей между исходной и новой картами, новая карта той же размерности. После этого в старшем разряде двоичных кодов наборов исходной карты добавляются незначащие нули, а в старшем разряде новой карты добавляются единицы. Эти две карты объединяются в одну большей размерности.
Если строится карта Карно для чётного количества переменных в наборе, то на расстоянии единицы снизу от исходной карты для нечётного количества переменных изображается повёрнутая на 180° вокруг оси, проходящей между исходной и новой картами, новая карта той же размерности. После этого в старшем разряде двоичных кодов наборов исходной карты добавляются незначащие нули, а в старшем разряде новой карты добавляются единицы. Эти две карты объединяются в одну большей размерности.
В картах наборы переменных, на которых функция принимает единичные значения, помечаются нечисловыми символами. Карта с нанесёнными на ней значениями ФАЛ называется диаграммой.
Карты, на которых коды наборов изображаются в восьмеричной системе счисления, называются картами Вейча.
Минимизация функций по методу Квайна
При минимизации по методу Квайна в базисе И, ИЛИ, НЕ исходная ФАЛ задаётся в СДНФ Целью минимизации является нахождение всех первичных импликант и выбор некоторых из них для минимальной записи функции.
Импликанта функции - некоторая логическая функция, обращаемая в нуль при наборе переменных, на котором сама функция также равна нулю.
Поэтому любой конъюнктивный терм, входящий в состав СДНФ, или группа термов, соединённых знаками дизъюнкции являются импликантами исходной ФАЛ. Импликанты имеют единичные значения только на подмножестве наборов из множества наборов, на которых исходная ФАЛ равна единице.
Первичная импликанта функции - импликанта типа элементарной конъюнкции некоторых переменных, никакая часть которой уже не является импликантой.
Задача минимизации по методу Квайна решается путём попарного сравнения всех импликант, входящих в ФАЛ, с целью выявления возможности их неполного склеивания по какой-то переменной на промежуточных этапах. При склеивании снижается ранг термов. Склеивание проводится до тех пор, пока не останется ни одного терма, допускающего склеивание с каким-либо другим термом. Термы, подвергшиеся склеиванию, отмечаются. Неотмеченные термы представляют собой первичные импликанты. После получения множества всех первичных импликант исследуется возможность нахождения простейшей записи ФАЛ. Для этого составляется таблица, в первой строке которой записаны минтермы исходной ФАЛ, а в первом столбце записаны все найденные первичные импликанты. Клетки этой таблицы помечаются в том случае, если первичная импликанта входит в состав какого-либо минтерма исходной ФАЛ. После этого задача упрощения сводится к тому, чтобы найти такое минимальное количество первичных импликант, которые покрывают все столбцы минтермов исходной ФАЛ.
Минимизация функций по методу Мак-Класки
Недостатком метода Квайна является - необходимость исчерпывающего попарного сравнения или сопоставления всех минтермов на этапе нахождения первичных импликант. С ростом числа минтермов увеличивается количество попарных сравнений.
Числовое представление ФАЛ позволяет упростить самый трудоёмкий первый этап. Все минтермы СДНФ ФАЛ записываются в виде их двоичных кодов, а все коды разбиваются по числу единиц на непересекающиеся группы.
Минтермы, подлежащие склеиванию, различаются только по одной переменной, а их коды - только в одном разряде. По этой причине сравнению подлежат только двоичные коды минтермов соседних групп.
Рассмотрев несколько методов минимизации ФАЛ, можно сделать вывод о том, что для решения нашей задачи наиболее подходящим является метод Мак-Класки.
Минимизируем Y:
Y=010001v010010v010011v010100v010101v010110v010111v011000v011001v110001v110010v110011v110100v110101v110110v110111v111000v111001
|
i |
x Q4Q3Q2Q1Q0 |
Восьмеричное число |
|
| 2 | 010001 | 21 | |
| 010010 | 22 | ||
| 010100 | 24 | ||
| 011000 | 30 | ||
| 3 | 010011 | 23 | |
| 010101 | 24 | ||
| 010110 | 26 | ||
| 011001 | 31 | ||
| 110001 | 61 | ||
| 110010 | 62 | ||
| 110100 | 64 | ||
| 111000 | 70 | ||
| 4 | 010111 | 27 | |
| 110011 | 63 | ||
| 110101 | 65 | ||
| 110110 | 66 | ||
| 111001 | 71 | ||
| 5 | 110111 | 67 |
Склеивание 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--
Минимизируем D4
D4 = 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 |
Д | ґ | ґ | ґ |
D4 = 0101-0v01100-v-01011v01011-v-10110v001-1-v0011--
Минимизируем D3
D3 = 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 |
Д | ґ | ґ | ґ |
D3 = 001000v00-110v-10001v100-11v0001--v-001-1v010-1-
Минимизируем D2
D2 = 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 |
ґ | ґ |
D2 = 010010v110110v1000-0v100-00v000-11v-00111
Минимизируем D1
D1 = 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 | Д | Д |
D1 = 001000v100111v110110v000-10v0-0010v-00010v00-101v1-0001v-01011
Минимизируем D0
D0 = 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 | ґ | Д | ґ | Д |
D0 = 011001v100101v110110v010-11v000--0v00-0-0v-000-0v00--10v001-1-
Заключение
Для получения оптимального варианта кодирования необходимо сопоставлять результаты минимизации комбинационных схем при использовании всех возможных вариантов кодирования.
Минимальный вариант построения принципиальной схемы может быть получен только после перебора и сравнения всех возможных вариантов построения цифрового устройства.
Для практического использования методов минимизации исключительное значение имеет инженерная интуиция при выборе вариантов кодирования и минимизации. Функции выхода цифрового автомата нужно задавать сравнительно редко, поскольку чаще всего применяются цифровые автоматы, не имеющие выходной комбинационной схемы. Для более сложных цифровых автоматов входная комбинационная схема, как правило, представляет собой преобразователь кода, или шифратор, состояния блок памяти цифрового автомата в выходной код цифрового автомата. Для большинства стандартных применений выходные комбинационные схемы цифровых автоматов минимизированы, разработаны и производятся в виде интегральных схем.
Таким образом, цель минимизации выходной комбинационной цифрового автомата зачастую сводится к выбору интегральных микросхем для конкретного использования.
Для структурного синтеза цифровых автоматов желательно применять табличные методы, так как они выполняются в более строгой форме, чем структурный синтез по графу, который требует огромного внимания на процессах синтеза и проверки его результатов. Количество ошибок при применении метода структурного синтеза по графу намного больше количества ошибок при использовании табличного метода структурного синтеза при всех прочих одинаковых условиях выполнения процесса синтеза.
В ходе выполнения курсовой работы было произведено построение кодопреобразователя по заданным входным и выходным функциям.
В процессе выполнения работы нами были приобретены практические навыки по курсам « Дискретная математика» и «Цифровые автоматы».
Литература
Гудилин А.В. Цифровая схемотехника. Челябинск, 2000.
Иванов В.И. Синтез цифровых автоматов для систем связи и управления. Челябинск, 1980
Щелкунов Н.Н., Дианов А.П. Процедуры программирования логических матриц, - Микропроцессорные средства и системы, 1986, №2.
Иванов В.И. Синтез цифровых автоматов для систем связи и управления, Челябинск, ЧПИ, 1980.
Баранов СИ. Синтез микропрограммных автоматов. - Л.: Энергия, 1979.
Электронный конспект лекций Гудилин Алексей Евгеньевич.
Конспект лекций по курсу цифровые автоматы. ЮУрГУ 2004.