Курсовая

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

Работа добавлена на сайт bukvasha.net: 2015-06-30

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 11.11.2024


Министерство образования и науки Российской Федерации

Южно-Уральский Государственный Университет

Кафедра Автоматики и Управления

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

по курсу: «Цифровые автоматы»

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

Руководитель Радкевич И. А.

« » 2007г.

Автор работы

студентка группы ЗФ-228-с

Ватутина /Лазуко/ А. Л.

« » 2007г.

Проект защищен с оценкой

_________________________

« » 2007г.

Челябинск 2007 год

Содержание

Задание

Введение

Понятие о дискретном (цифровом) автомате.

Основные понятия алгебры логики.

Понятия теории графов

Граф-дерево автомата Мура.

Граф-дерево автомата Мили.

Таблица переходов по автомату Мили

Таблица выходов по автомату Мили

Минимизация цифрового автомата Мили.

Таблица переходов с распределением неопределённостей.

Исключение недостижимых состояний.

Определение класса совместимости.

Классы единичной совместимости

Классы двоичной совместимости

Классы троичной совместимости

Классы четверичной совместимости

Классы пятеричной совместимости

Таблица состояний и выходов нормализованного автомата

Структурный синтез цифрового автомата

Выбор триггера

Представление функции возбуждения

Таблица состояний и выходов нормализованного автомата

Минимизирующие карты

Минимизация функций по методу Квайна

Минимизация функций по методу Мак-Класки

Заключение

Литература

Задание

Построить устройство для преобразования последовательного двоично-десятичного кода X = (хЗ, х2, х1, х0), который подаётся на вход устройства z = (z3, z2, z1, z0). Десятичный эквивалент X двоично-десятичного кода может быть вычислен: Х=Ë xi pi , где xi = 0, 1 - цифра двоично-десятичного кода, a pi - вес i-ro разряда.

Вариант задания представлен в таблице:

Номер варианта

X

Р3Р2Р1P0

z

Р3Р2Р1P0

24

4311

5211

Цель

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

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

Введение

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

На первом уровне реализации работы была составлена таблица соответствий входного и выходного сигналов для десяти заданных значений и произведены преобразования для соблюдения условия автоматности.

На следующем уровне работы было произведено построение граф-деревьев абстрактных автоматов Мура и Мили. Затем по графу составлены таблицы переходов и выходов для автомата Мили.

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

На четвёртом уровне работы был произведён структурный синтез цифрового автомата с кодированием двоичным кодом входной, выходной функций автомата, а также функции состояний. Определена таблица состояний выбранного для реализации кодопреобразователя D-триггера.

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

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

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

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

КСВХ - входная комбинационная схема; П - память; КсВЬ1Х - выходная комбинационная схема; Х- входной цифровой код; В - код возбуждения памяти; А - код состояния памяти; Y - выходной код.

Рис.1. Каноническая структурная схема цифрового автомата

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

Понятие о дискретном (цифровом) автомате.

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

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

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

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

Цифровой автомата (первого или второго рода) называется правильным, если выходной сигнал y(t) определяется одним лишь его состоянием (a(t-1) или a(t)) и не зависит явно от входного сигнала x(t). Автоматы первого рода обычно также называют автоматами Мили, по имени американского ученого, который впервые начал их систематическое изучение. Особый интерес на практике имеют правильные автоматы второго рода, известные обычно под более кратким названием автоматов Мура.

Основные понятия алгебры логики.

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

Для формального описания цифровых автоматов применяется аппарат алгебры логики, созданной английским математиком Дж. Булем (1815-1864). Поэтому алгебру логики называют алгеброй Буля или булевой алгеброй.

В алгебре логики применительно к описанию цифровых автоматов, работающих в двоичном представлении кодов (или цифровой информации) основными понятиями являются логическая (булева) переменная и логическая функция (функция алгебры логики - ФАЛ).

Логическая (булева) переменная - такая величина х, которая может принимать только два значения: х = {0,1}.

Логическая функция (функция алгебры логики - ФАЛ) - функция многих аргументов f(xn-1, хn-2, ..., х0), принимающая значения равные нулю или единице на наборах логических переменных xn-1, хn-2, ..., х0.

В дальнейшем в формальных описаниях наборов переменных и логических функций сами наборы переменных интерпретируются как двоичные коды (числа). В двоичных кодах расположение логических переменных упорядочено в порядке уменьшения индекса слева направо, и каждая логическая переменная имеет вес в зависимости от позиции в коде, увеличивающийся справа налево. Вес каждой i-той логической переменной, являющейся значением разряда двоичного числа равен 2i (i = 0,...,n-l).

Для n-разрядного кода общее количество уникальных наборов переменных: N = 2n (1)

Максимальное числовое значение двоичного кода равно: Aмакс=2n - 1 (2)

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

Таблица 1

X

f0(x)

f1(x)

f2(x)

f3(x)

0

0

0

1

1

1

0

1

0

1

Функция f0(x) называется константой нуля, а функция f3(x) - константой единицы. Функция fi(x), повторяющая значения логической переменной, - тождественная функция (fi(x)=x), а функция f2(x), принимающая значения, обратные значениям переменной х, - логическое отрицание или инверсия (НЕ) (f2(x) =).

Элементы алгебры логики имеют следующие операции:

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

Дизъюнкция (ИЛИ, логическая сумма) - сумма двух высказываний Р и Q; результатом является ложное высказывание, если оба высказывания ложные, и истинное во всех других случаях.

Инверсия (отрицание) - отрицанием высказывания Р называется высказывание истинное, если само высказывание Р ложное, или наоборот.

Для функции двух переменных, согласно ф.(1), существует четыре уникальных набора переменных. Функции отличаются друг от друга набором значений 0 и 1 в четырех разрядах кода значений функции. Общее количество функций на п-местном или п-разрядном наборе переменных равно: (3).

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

Аналитически это свойство описывается следующей формулой:

f1(xn-1, xn-2, …, x0) = f1(xn-1, xn-2, …, x0) (4)

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

Система булевых функций W называется функционально полной, если для любой булевой функции п-переменных f(xn-1, хn-2, ..., х0) может быть построена равносильная ей функция комбинированием булевых переменных xn-1, хn-2, ..., х0 и функций системы W, взятых в любом конечном количестве экземпляров каждая. Такая система булевых функций (W) называется базисом.

Таким образом, базис - полная система функций алгебры логики (ФАЛ), с помощью которой любая ФАЛ может быть представлена суперпозицией исходных функций W.

Базисом является система функций И (конъюнкция), ИЛИ (дизъюнкция), НЕ, (инверсия), свойства которых были впервые изучены Дж. Булем.

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

Для абстрактного математического описания цифрового автомата как кодопреобразователя используется представление 6-элементного множества S = {А, Х,У, d, l, a1,}.

Понятие множества - понятие, которое не имеет определения. Множества имеют свои подмножества, оно может быть конечным и бесконечным. Упорядоченным будет множество, в котором каждый элемент имеет своё место.

Множество будет состоять из следующих элементов:

А = {а1...,ап} -множество состояний автомата,

X = {х1...,хп} - множество входных сигналов,

Y = {у1.. .,уп} - множество выходных сигналов,

d - функция переходов абстрактного цифрового автомата,

l - функция выходов абстрактного цифрового автомата,

a1 - начальное состояние автомата (ai принадлежит А).

Для однозначного управления цифровым автоматом необходимо, чтобы он начинал работу с определённого начального состояния. Автомат является конечным, если А, X и Y не являются бесконечными множествами. Теоретически все элементы множеств А, X, Y могут быть закодированы числами в системе счисления с любым основанием, но на практике всегда используется двоичная система счисления. Согласно структурной схеме (рис.1), коды наборов переменных комбинационных схем определяются в результате конкатенации кодов входных сигналов и кодов состояний блока памяти. Как наборы входных переменных, так и коды состояний блока памяти в общем случае содержат запрещённые комбинации, поэтому системы функций алгебры логики, описывающие комбинационные схемы, не будут полностью определёнными.

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

Десятичные цифры

Входной код 4311

Выходной код 5311

0

0000

0000

1

0001

0001

2

0010

0010

3

0011

0011

4

0100

0100

5

0101

0101

6

1000

1010

7

1001

1011

8

1100

1110

9

1101

1111

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

  1. Длина входного слова должна соответствовать длине выходного слова. В общем случае при несоответствии входного и выходного слов недостающие фрагменты заполняются пустыми символами (0);

  2. Минимум три первых символа входных и выходных слов должны соответствовать друг другу. В нашем случае это условие частично не выполняется, поэтому для соблюдения условия автоматности кодопреобразователя к входному и выходному словам добавим пустые символы (0).

При этом таблица соответствия примет вид:

Десятичные цифры

Входной код 4311

Выходной код 5311

0

0000000

0000000

1

0001000

0000001

2

0010000

0000010

3

0011000

0000011

4

0100000

0000100

5

0101000

0000101

6

1000000

0001010

7

1001000

0001011

8

1100000

0001110

9

1101000

0001111

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

- при описании функционирования автомата выражениями:

a(t+l) = 5[a(t),z(t)],

w(t) = l[a(t), z(t)] - он называется автоматом Мили;

- при описании функционирования автомата выражениями:

a(t+1) = d[a(t),z(t)],

w(t) = l[а(t)] - он называется автоматом Мура.

В этих выражениях t - текущий момент дискретного автоматного времени, t+1 -следующий момент дискретного автоматного времени.

Понятия теории графов

Графами называют взаимосвязь двух множеств состоящих из множества вершин и множества рёбер, индуцируемых (связанных) между собой.

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

Неориентированный граф - граф, не имеющий указания направлений ребер, при переходе из одной вершины в другую.

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

Граф-дерево - это слабосвязанный граф, у которого если удалить одно ребро, то он распадается на два графа.

Граф автомата - ориентированный связный граф, вершины которого соответствуют состояниям, а дуги - переходам между ними.

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

Две вершины графа автомата ат и as (исходное состояние и состояние перехода) соединяются дугой (ребром), направленной от ат в as. Дуге (ат, as) графа автомата приписывается входной сигнал х и выходной сигнал у, если он определён, и, в противном случае, ставится прочерк. Если переход автомата из состояния ат в состояние as происходит под действием нескольких входных сигналов, то дуге (am, as) приписываются все эти входные и соответствующие выходные сигналы.

При описании автомата Мура в виде графа выходной сигнал y записывается внутри вершины ат или рядом с ней, а входной сигнал х над дугой (ребром), демонстрирующей переход из одного состояния в другое.

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

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

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

Устойчивым состоянием автомата называется такое состояние, что для любого х, d(am, x) = as, имеет место d(as, x) = as. Это значит, что если автомат перешёл в некоторое состояние х, то выйти из этого состояния может только под действием другого сигнала.

Синхронным называется автомат, если он не является асинхронным и каждое его состояние устойчиво.

Если для некоторой пары (am, zf) выходной сигнал автомата не определён, то для этой пары не определяется и функция перехода, так как не определено допустимое слово, осуществляющее переход из этого состояния.

Граф-дерево автомата Мура.

Для построения графа-дерево автомата Мура используем таблицу соответствия, дополненную до выполнения условия автоматности. После выполнения условия автоматности граф-дерево примет вид:

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

Граф-дерево автомата Мили.

10



В ходе этапа построения кодопреобразователя осуществляется преобразование графа-дерево автомата Мура в граф-дерево автомата Мили. Для этого все конечные состояния автомата Мура заменяются нулевым состоянием. Граф-дерево автомата Мили:

Таблица переходов по автомату Мили

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

x/a

a0

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

a14

a15

a16

a17

a18

a19

a20

a21

0

a1

a3

a5

a7

a9

a10

a11

a12

a14

a16

a18

a20

a22

a23

a24

a25

a26

a27

a28

a29

a30

a31

1

a2

a4

a6

a8

-

-

-

a13

a15

a17

a19

a21

-

-

-

-

-

-

-

-

-

-

x/a

a22

a23

a24

a25

a26

a27

a28

a29

a30

a31

a32

a33

a34

a35

a.36

a37

a38

a39

a40

a41

0

a32

a33

a34

a35

a36

a37

a38

a39

a40

a41

a0

a0

a0

a0

a0

a0

a0

a0

a0

a0

1

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

Таблица выходов по автомату Мили

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

x/a

a0

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

a14

a15

a16

a17

a18

a19

a20

a21

0

0

0

0

0

0

0

0

0

0

0

1

1

0

0

0

0

1

1

0

0

1

1

1

0

0

0

0

-

-

-

0

0

0

1

1

-

-

-

-

-

-

-

-

-

-

x/a

a22

a23

a24

a25

a26

a27

a28

a29

a30

a31

a32

a33

a34

a35

a.36

a37

a38

a39

a40

a41

0

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

1

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

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

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

Минимизация цифрового автомата Мили.

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

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

Полностью определённый автомат является частным случаем частичного автомата.

Таблица переходов с распределением неопределённостей.

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

Исключение недостижимых состояний.

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

Определение класса совместимости.

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

Состояния называются i-совместимыми для i=1, 2,..., если результат применения к этим состояниям любого слова длины i будет одинаковым. Классы совместимых состояний могут быть найдены непосредственно по таблице выходов. В один и тот же 1 - класс зачисляются состояния, обозначающие совпадающие (с точностью до неопределённых выходных сигналов) столбцы таблицы выходов. Классы (i+1) - совместимости получаются из классов i - совместимости путём их расщепления на классы (i+1) - совместимости. Для этого у каждого состояния, принадлежащего j - классу i - совместимости Cj(i), номера классов (индексы), в которые автомат переходит под воздействием каждой входной буквы. Если номер класса не определён, то ставится специальный символ, например, прочерк. Индексы классов, в которые переходит автомат под действием входного сигнала, образуют отметку. Множество состояний с одинаковыми отметками в классе Cj(i) образуют классы (i+1) - совместимости. При выполнении операции расщепления классов специальный символ неопределённости может быть заменён номером (индексом) любого класса. Если операцию расщепления i-классов применить последовательно, начиная с 1-класса, то через конечное число шагов процесс расщепления закончится. Нерасщепляемые далее классы образуют классы совместимых состояний. Иногда отметки состояний разных классов совпадают, но объединять такие состояния в один класс (i+1) - совместимости совершенно недопустимо.

Задачей минимизации методом расщепления классов является получение как можно меньшего количества и как можно большей ёмкости классов конечной совместимости.

Классы единичной совместимости

В классы единичной совместимости поместим:

C1(1)

0

1

0

1

1

1

1

1

2

1

1

3

1

1

4

1

-

5

2

-

6

2

-

7

1

1

8

1

1

9

2

2

12

1

-

13

1

-

14

2

-

15

2

-

18

2

-

19

2

-

22

1

-

23

2

-

26

1

-

27

2

-

32

1

-

34

1

-

36

1

-

38

1

-

40

1

-

C2(1)

0

1

10

1

1

11

2

2

16

1

-

17

1

-

20

2

-

21

2

-

24

1

-

25

2

-

28

1

-

29

2

-

30

1

-

31

2

-

33

1

-

35

1

-

37

1

-

39

1

-

41

1

-



Видим, что в таблицах есть несовместимые переходы классов, поэтому продолжим разбиение.

Классы двоичной совместимости

D1(2)

0

1

0

1

1

1

1

1

2

2

2

3

1

1

4

2

-

7

1

1

8

2

2

12

1

-

13

2

-

22

3

-

26

3

-

D2(2)

0

1

5

4

-

6

6

-

9

4

4

14

4

-

15

6

-

18

4

-

19

6

-

23

5

-

27

5

-

D3(2)

0

1

32

1

-

34

1

-

36

1

-

38

1

-

40

1

-

D5(2)

0

1

33

1

-

35

1

-

37

1

-

39

1

-

41

1

-

D6(2)

0

1

11

6

6

20

4

-

21

6

-

25

5

-

29

5

-

31

5

-


D4(2)

0

1

10

2

2

16

1

-

17

2

-

24

3

-

28

3

-

30

3

-
Видим, что в таблицах есть несовместимые переходы классов, поэтому продолжим разбиение.

E10(3)

0

1

24

7

-

28

7

-

30

7

-




E12(3)

0

1

11

13

12

21

14

-




E13(3)

0

1

20

10

-




E14(3)

0

1

25

11

-

29

11

-

31

11

-
Классы троичной совместимости

E1(3)

0

1

0

1

2

1

1

2

3

1

2

7

1

2

12

3

-




E2(3)

0

1

2

4

5

4

4

-

8

4

5

13

6

-

E3(3)

0

1

22

7

-

26

7

-




E4(3)

0

1

5

8

-

9

9

8

14

10

-

18

10

-




E5(3)

0

1

6

12

-

15

14

-

19

14

-

E7(3)

0

1

32

1

-

34

1

-

36

1

-

38

1

-

40

1

-




E8(3)

0

1

10

4

5

17

6

-




E9(3)

0

1

16

3

-

E6(3)

0

1

23

11

-

27

11

-

E11(3)

0

1

33

1

-

35

1

-

37

1

-

39

1

-

41

1

-


F21(4)

0

1

11

23

22




F22(4)

0

1

21

24

-




F23(4)

0

1

20

19

-




F24(4)

0

1

25

20

-

29

20

-

31

20

-
Классы четверичной совместимости

F1(4)

0

1

0

2

6




F2(4)

0

1

1

3

6




F3(4)

0

1

3

4

6




F5(4)

0

1

12

8

-




F6(4)

0

1

2

9

12

4

10

-

8

11

13




F7(4)

0

1

13

14

-




F8(4)

0

1

22

15

-

26

15

-




F9(4)

0

1

5

16

-




F10(4)

0

1

9

18

17




F11(4)

0

1

14

19

-

18

19

-




F12(4)

0

1

6

21

-
F13(4)

0

1

15

24

-

19

24

-




F14(4)

0

1

23

20

-

27

20

-




F15(4)

0

1

32

1

-

34

1

-

36

1

-

38

1

-

40

1

-




F16(4)

0

1

10

11

13




F17(4)

0

1

17

14

-




F18(4)

0

1

16

8

-




F19(4)

0

1

24

15

-

28

15

-

30

15

-




F20(4)

0

1

33

1

-

35

1

-

37

1

-

39

1

-

41

1

-



Классы пятеричной совместимости

G1(5)

0

1

0

2

6




G2(5)

0

1

1

3

7




G3(5)

0

1

3

4

8




G4(5)

0

1

7

5

9




G5(5)

0

1

12

10

-




G6(5)

0

1

2

11

14




G7(5)

0

1

4

12

-




G8(5)

0

1

8

12

15




G9(5)

0

1

13

16

-




G10(5)

0

1

22

17

-

26

17

-




G11(5)

0

1

5

18

-



G12(5)

0

1

9

20

19




G13(5)

0

1

14

21

-

18

21

-




G14(5)

0

1

6

23

-

G15(5)

0

1

15

26

-

19

26

-




G16(5)

0

1

23

22

-

27

22

-




G17(5)

0

1

32

1

-

34

1

-

36

1

-

38

1

-

40

1

-




G18(5)

0

1

10

13

15




G19(5)

0

1

17

16

-




G20(5)

0

1

16

10

-




G21(5)

0

1

24

17

-

28

17

-

30

17

-




G22(5)

0

1

33

1

-

35

1

-

37

1

-

39

1

-

41

1

-




G23(5)

0

1

11

25

24




G24(5)

0

1

21

26

-





G25(5)

0

1

20

21

-




G26(5)

0

1

25

22

-

29

22

-

31

22

-

При построении нормализованного автомата переход d = (Ci, zj) считается неопределённым, если для всех состояний этого класса не определены переходы в другое состояние. Если хотя бы для одного состояния класса переход определён, то в клетку таблицы нормализованного автомата заносится индекс класса, в который переходит цифровой автомат из этого состояния. Таким образом, доопределяются неопределённые переходы исходного автомата. Нормализованный автомат является эквивалентным любому из минимизированных автоматов и не имеет, как минимум, ни одной пары совместимых состояний. В соответствии с изложенной методикой минимизации получаются либо полностью определённые, либо частичные нормализованные автоматы.

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

Таблица состояний и выходов нормализованного автомата

Вх/сост

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

-/-

-/-

-/-


В результате всех преобразований мы получили нормализованный минимизированный автомат, по которому построим граф автомата Мили:

Структурный синтез цифрового автомата

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

Задачей этапа структурного синтеза является построение принципиальной схемы автомата из элементарных автоматов заданного типа. Элементарные автоматы подразделяются на два больших класса:

  • элементарные автоматы памяти (запоминающие элементы);

  • элементарные автоматы без памяти (элементарные комбинационные схемы или логические элементы).

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

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

Если автомат имеет М состояний, то для двоичного структурного алфавита количество триггеров в блоке памяти этого автомата

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 =

D4 =

v010110v010111v011000v011001v101011v110110

D3 =

v010011v010110v010111v100011v100101v100111v110001

D2 =

D1 =

V100001v100010v100111v101011v110001v110110

D0 =

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

Минимизирующие карты

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

Если строится карта Карно для чётного количества переменных в наборе, то на расстоянии единицы снизу от исходной карты для нечётного количества переменных изображается повёрнутая на 180° вокруг оси, проходящей между исходной и новой картами, новая карта той же размерности. После этого в старшем разряде двоичных кодов наборов исходной карты добавляются незначащие нули, а в старшем разряде новой карты добавляются единицы. Эти две карты объединяются в одну большей размерности.

В картах наборы переменных, на которых функция принимает единичные значения, помечаются нечисловыми символами. Карта с нанесёнными на ней значениями ФАЛ называется диаграммой.

Карты, на которых коды наборов изображаются в восьмеричной системе счисления, называются картами Вейча.

Минимизация функций по методу Квайна

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

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

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

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

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

Минимизация функций по методу Мак-Класки

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

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

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

Рассмотрев несколько методов минимизации ФАЛ, можно сделать вывод о том, что для решения нашей задачи наиболее подходящим является метод Мак-Класки.

Минимизируем Y:

Y=

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-

Заключение

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

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

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

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

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

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

В процессе выполнения работы нами были приобретены практические навыки по курсам « Дискретная математика» и «Цифровые автоматы».

Литература

  1. Гудилин А.В. Цифровая схемотехника. Челябинск, 2000.

  2. Иванов В.И. Синтез цифровых автоматов для систем связи и управления. Челябинск, 1980

  3. Щелкунов Н.Н., Дианов А.П. Процедуры программирования логических матриц, - Микропроцессорные средства и системы, 1986, №2.

  4. Иванов В.И. Синтез цифровых автоматов для систем связи и управления, Челябинск, ЧПИ, 1980.

  5. Баранов СИ. Синтез микропрограммных автоматов. - Л.: Энергия, 1979.

  6. Электронный конспект лекций Гудилин Алексей Евгеньевич.

  7. Конспект лекций по курсу цифровые автоматы. ЮУрГУ 2004.


1. Контрольная работа на тему Правовое положение свидетелей
2. Реферат Физиология легочного дыхания
3. Отчет по практике Отчет по практике в ЗАО НАР
4. Контрольная работа Экономический рост 21
5. Реферат на тему Joan Of Arc 2 Essay Research Paper
6. Курсовая на тему Удаление отходов населения
7. Диплом Совершенствование системы финансового планирования организации
8. Курсовая Расчет и подбор нормализованного теплообменного аппарата
9. Отчет по практике Маркетинговая деятельность предприятия 2 Характеристика организационной
10. Реферат Вышеславцев, Никита Васильевич