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

13

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

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

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

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

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

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

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

« » 2007г.

Автор работы

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

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

« » 2007г.

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

_________________________

« » 2007г.

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

Содержание

• Задание 2
• Введение 2
• Понятие о дискретном (цифровом) автомате. 4
• Основные понятия алгебры логики. 5
• Понятия теории графов 10
• • Граф-дерево автомата Мура. 12
  • Граф-дерево автомата Мили. 13
  • Таблица переходов по автомату Мили 14
  • Таблица выходов по автомату Мили 14
• Минимизация цифрового автомата Мили. 15
• • Таблица переходов с распределением неопределённостей. 15
  • Исключение недостижимых состояний. 15
• Определение класса совместимости. 16
• • Классы единичной совместимости 17
  • Классы двоичной совместимости 18
  • Классы троичной совместимости 18
  • Классы четверичной совместимости 19
  • Классы пятеричной совместимости 20
• Таблица состояний и выходов нормализованного автомата 21
• Структурный синтез цифрового автомата 22
• Выбор триггера 23
• Представление функции возбуждения 25
• • Таблица состояний и выходов нормализованного автомата 27
• Минимизирующие карты 30
• Минимизация функций по методу Квайна 31
• Минимизация функций по методу Мак-Класки 32
• Заключение 43
• Литература 44

Задание

• Построить устройство для преобразования последовательного двоично-десятичного кода X = (х_З, х₂, х₁, х₀), который подаётся на вход устройства z = (z₃, z₂, z₁, z₀). Десятичный эквивалент X двоично-десятичного кода может быть вычислен: Х=E x_i p_i , где x_i = 0, 1 - цифра двоично-десятичного кода, a p_i - вес i-ro разряда.

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

Цель

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

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

• Введение

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

• На первом уровне реализации работы была составлена таблица соответствий входного и выходного сигналов для десяти заданных значений и произведены преобразования для соблюдения условия автоматности.
• На следующем уровне работы было произведено построение граф-деревьев абстрактных автоматов Мура и Мили. Затем по графу составлены таблицы переходов и выходов для автомата Мили.
• На третьем уровне работы произведена минимизация автомата Мили путём составления таблицы переходов с распределением неопределённостей, исключением недостижимых состояний проектируемого автомата, определение классов совместимости до получения нормализованного автомата, построение графа полученного автомата.
• На четвёртом уровне работы был произведён структурный синтез цифрового автомата с кодированием двоичным кодом входной, выходной функций автомата, а также функции состояний. Определена таблица состояний выбранного для реализации кодопреобразователя D-триггера.
• Пятым этапом выполнения работы была минимизация с помощью диаграмм Вейча, функций выхода кодопреобразователя и возбуждения D-триггера, а также их реализация в базисе И, ИЛИ, НЕ.
• На последнем уровне работы была составлена схема последовательного кодопреобразователя заданного входного кода в заданный выходной на простейших цифровых автоматах с памятью.
• Особенностью цифрового автомата является зависимость оператора преобразования А от предыдущих состояний кодопреобразователя, то есть наличие памяти у цифрового автомата. В частном случае отсутствия памяти у цифрового автомата, он является логической схемой. Таким образом, предметами исследования в теории цифровых автоматов являются как собственно цифровые автоматы (системы с памятью), так и автоматы без памяти или логические схемы.
• Наиболее разработана теория цифровых автоматов применительно к канонической структуре цифрового автомата, представленной на рис.1. Для дальнейшего рассмотрения используется только эта структура цифрового автомата.
• КС_ВХ - входная комбинационная схема; П - память; Кс_ВЬ1Х - выходная комбинационная схема; Х- входной цифровой код; В - код возбуждения памяти; А - код состояния памяти; Y - выходной код.
• Рис.1. Каноническая структурная схема цифрового автомата
• По структурной схеме цифрового автомата видно, что входные коды входной и выходной комбинационных схем получаются в результате конкатенации (объединения) входного кода и кода состояния памяти цифрового автомата.

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

• Дискретными автоматами принято называть устройства, служащие для преобразования дискретной информации. В современных цифровых автоматах принято обычно отождествлять буквы используемого стандартного алфавита с цифрами той или иной системы счисления (чаще всего двоичной или десятичной). Поэтому дискретные автоматы принято также называть цифровыми автоматами.
• Основным качеством, выделяющим дискретные автоматы из числа всех других преобразователей информации, является наличие дискретного (при этом реальных автоматах всегда конечного) множества внутренних состояний и свойства скачкообразного перехода автомата из одного состояния в другое. Скачкообразность перехода означает возможность трактовать этот переход как мгновенный, причем как такой, который совершается непосредственно, минуя какие-либо промежуточные состояния.
• Изменения состояний цифрового автомата называются входными сигналами, возникающими вне автомата и передающимися в автомат по конечному числу входных каналов.
• Результатом работы цифрового автомата является выдача выходных сигналов, передаваемых из автомата во внешние цепи по конечному числу выходных каналов.
• Цифровой автомата (первого или второго рода) называется правильным, если выходной сигнал y(t) определяется одним лишь его состоянием (a(t-1) или a(t)) и не зависит явно от входного сигнала x(t). Автоматы первого рода обычно также называют автоматами Мили, по имени американского ученого, который впервые начал их систематическое изучение. Особый интерес на практике имеют правильные автоматы второго рода, известные обычно под более кратким названием автоматов Мура.
• Основные понятия алгебры логики.
• Понятие цифрового автомата было введено как модель для описания функционирования устройств, предназначенных для переработки цифровой или дискретной информации.
• Для формального описания цифровых автоматов применяется аппарат алгебры логики, созданной английским математиком Дж. Булем (1815-1864). Поэтому алгебру логики называют алгеброй Буля или булевой алгеброй.
• В алгебре логики применительно к описанию цифровых автоматов, работающих в двоичном представлении кодов (или цифровой информации) основными понятиями являются логическая (булева) переменная и логическая функция (функция алгебры логики - ФАЛ).
• Логическая (булева) переменная - такая величина х, которая может принимать только два значения: х = {0,1}.
• Логическая функция (функция алгебры логики - ФАЛ) - функция многих аргументов f(x_n-1, х_n-2, ..., х₀), принимающая значения равные нулю или единице на наборах логических переменных x_n-1, х_n-2, ..., х₀.
• В дальнейшем в формальных описаниях наборов переменных и логических функций сами наборы переменных интерпретируются как двоичные коды (числа). В двоичных кодах расположение логических переменных упорядочено в порядке уменьшения индекса слева направо, и каждая логическая переменная имеет вес в зависимости от позиции в коде, увеличивающийся справа налево. Вес каждой i-той логической переменной, являющейся значением разряда двоичного числа равен 2i (i = 0,...,n-l).
• Для n-разрядного кода общее количество уникальных наборов переменных: N = 2ⁿ (1)
• Максимальное числовое значение двоичного кода равно: A_макс=2ⁿ - 1 (2)
• Значения всех логических функций от одной переменной представлены в таблице 1.

Таблица 1

• Функция f₀(x) называется константой нуля, а функция f₃(x) - константой единицы. Функция f_i(x), повторяющая значения логической переменной, - тождественная функция (f_i(x)=x), а функция f₂(x), принимающая значения, обратные значениям переменной х, - логическое отрицание или инверсия (НЕ) (f₂(x) =).
• Элементы алгебры логики имеют следующие операции:
• Конъюнкция (И, логическое умножение) - произведение двух высказываний Р и Q, результатом которого является истина, если оба высказывания истинны и ложь во всех других случаях.
• Дизъюнкция (ИЛИ, логическая сумма) - сумма двух высказываний Р и Q; результатом является ложное высказывание, если оба высказывания ложные, и истинное во всех других случаях.
• Инверсия (отрицание) - отрицанием высказывания Р называется высказывание истинное, если само высказывание Р ложное, или наоборот.
• Для функции двух переменных, согласно ф.(1), существует четыре уникальных набора переменных. Функции отличаются друг от друга набором значений 0 и 1 в четырех разрядах кода значений функции. Общее количество функций на п-местном или п-разрядном наборе переменных равно: (3).
• Две функции равносильны друг другу, если они принимают на всех возможных наборах переменных одни и те же значения.

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

• f₁(x_n-1, x_n-2, …, x₀) = f₁(x_n-1, x_n-2, …, x₀) (4)
• Обе функции в ф.(4) могут иметь разные формы аналитической записи, но практически наиболее выгодной будет самая простая форма записи.
• Система булевых функций W называется функционально полной, если для любой булевой функции п-переменных f(x_n-1, х_n-2, ..., х₀) может быть построена равносильная ей функция комбинированием булевых переменных x_n-1, х_n-2, ..., х₀ и функций системы W, взятых в любом конечном количестве экземпляров каждая. Такая система булевых функций (W) называется базисом.
• Таким образом, базис - полная система функций алгебры логики (ФАЛ), с помощью которой любая ФАЛ может быть представлена суперпозицией исходных функций W.
• Базисом является система функций И (конъюнкция), ИЛИ (дизъюнкция), НЕ, (инверсия), свойства которых были впервые изучены Дж. Булем.

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

• Для абстрактного математического описания цифрового автомата как кодопреобразователя используется представление 6-элементного множества S = {А, Х,У, , , a₁,}.
• Понятие множества - понятие, которое не имеет определения. Множества имеют свои подмножества, оно может быть конечным и бесконечным. Упорядоченным будет множество, в котором каждый элемент имеет своё место.
• Множество будет состоять из следующих элементов:
• А = {а₁...,а_п} -множество состояний автомата,
• X = {х₁...,х_п} - множество входных сигналов,
• Y = {у₁.. .,у_п} - множество выходных сигналов,
• - функция переходов абстрактного цифрового автомата,
• - функция выходов абстрактного цифрового автомата,
• a₁ - начальное состояние автомата (a_i принадлежит А).
• Для однозначного управления цифровым автоматом необходимо, чтобы он начинал работу с определённого начального состояния. Автомат является конечным, если А, 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

  • При рассмотрении конечного автомата необходимо рассмотреть условие автоматности, то есть выполнение следующих условий:
  • Длина входного слова должна соответствовать длине выходного слова. В общем случае при несоответствии входного и выходного слов недостающие фрагменты заполняются пустыми символами (0);
  • Минимум три первых символа входных и выходных слов должны соответствовать друг другу. В нашем случае это условие частично не выполняется, поэтому для соблюдения условия автоматности кодопреобразователя к входному и выходному словам добавим пустые символы (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) = [a(t), z(t)] - он называется автоматом Мили;
    • - при описании функционирования автомата выражениями:
    • a(t+1) = [a(t),z(t)],
    • w(t) = [а(t)] - он называется автоматом Мура.
    • В этих выражениях t - текущий момент дискретного автоматного времени, t+1 -следующий момент дискретного автоматного времени.
    • Понятия теории графов
    • Графами называют взаимосвязь двух множеств состоящих из множества вершин и множества рёбер, индуцируемых (связанных) между собой.
    • Полный граф - это граф, не имеющий петель, кратности ребер, и все его вершины связаны между собой.
    • Неориентированный граф - граф, не имеющий указания направлений ребер, при переходе из одной вершины в другую.
    • Ориентированный (полный) граф - граф с ребрами, указывающими конкретное направление при переходе из одной вершины в другую.
    • Граф-дерево - это слабосвязанный граф, у которого если удалить одно ребро, то он распадается на два графа.
    • Граф автомата - ориентированный связный граф, вершины которого соответствуют состояниям, а дуги - переходам между ними.
    • Теория графов имеет большие приложения, так как язык теории, с одной стороны, очевиден, а, с другой стороны, удобен в нормальном исследовании. При полном изображении графа не все детали рисунка имеют одинаковое значение, а именно геометрические свойства рёбер (кривизна, длина и т.д.) и расположение вершин на плоскости относительно друг друга.
    • Две вершины графа автомата а_т и a_s (исходное состояние и состояние перехода) соединяются дугой (ребром), направленной от а_т в a_s. Дуге (а_т, a_s) графа автомата приписывается входной сигнал х и выходной сигнал у, если он определён, и, в противном случае, ставится прочерк. Если переход автомата из состояния а_т в состояние a_s происходит под действием нескольких входных сигналов, то дуге (a_m, a_s) приписываются все эти входные и соответствующие выходные сигналы.
    • При описании автомата Мура в виде графа выходной сигнал y записывается внутри вершины а_т или рядом с ней, а входной сигнал х над дугой (ребром), демонстрирующей переход из одного состояния в другое.
    • При описании автомата Мили в виде графа внутри вершины записывается состояние, в которое переходит автомат, а над дугой (ребром), демонстрирующей переход из одного состояния автомата в другое, записывается дробь, в числителе которой указывается входной сигнал, а в знаменателе - выходной сигнал.
    • Для задания функций переходов и выходов построим граф-дерево автомата Мура, а затем автомата Мили. При использовании табличного описания автомата Мура таблицы переходов автоматов Мили и Мура совпадут, а таблица выходов автомата Мили получится из таблицы переходов заменой a_s символом выходного сигнала.
    • В технических целях используются только детерминированные цифровые автоматы, в которых выполнено условие однозначности переходов: - автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Применительно к табличному способу задания описания автоматов это означает, что в клетках переходов/выходов указывается только по одному состоянию/выходному сигналу. Применительно к графическому способу задания описания автоматов это означает, что в графе автомата из любой вершины не могут выходить две или более дуги, отмеченные одним и тем же входным сигналом.
    • Устойчивым состоянием автомата называется такое состояние, что для любого х, (a_m, x) = a_s, имеет место (a_s, x) = a_s. Это значит, что если автомат перешёл в некоторое состояние х, то выйти из этого состояния может только под действием другого сигнала.
    • Синхронным называется автомат, если он не является асинхронным и каждое его состояние устойчиво.
    • Если для некоторой пары (a_m, z_f) выходной сигнал автомата не определён, то для этой пары не определяется и функция перехода, так как не определено допустимое слово, осуществляющее переход из этого состояния.
    • Граф-дерево автомата Мура.
    • Для построения графа-дерево автомата Мура используем таблицу соответствия, дополненную до выполнения условия автоматности. После выполнения условия автоматности граф-дерево примет вид:
    • Два автомата с одинаковыми входным и выходным алфавитами называются эквивалентными, если после установки начального состояния их реакции на любое входное слово совпадают. Отсюда следует, что для любого автомата Мили существует эквивалентный автомат Мура, и, обратно, для любого автомата Мура существует эквивалентный ему автомат Мили. Таким образом, возможны взаимные трансформации автоматов.
    • Граф-дерево автомата Мили.

    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

      -

      -

      -

      -

      -

      -

      -

      -

      -

      -

      -

      -

      -

      -

      -

      -

      -

      -

      -

      -

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

      • 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 и a_j называются совместимыми, если, двигаясь из этих состояний под воздействием любого входного сигнала, автомат индуцирует одинаковое его отображение.
        • Состояния называются i-совместимыми для i=1, 2,..., если результат применения к этим состояниям любого слова длины i будет одинаковым. Классы совместимых состояний могут быть найдены непосредственно по таблице выходов. В один и тот же 1 - класс зачисляются состояния, обозначающие совпадающие (с точностью до неопределённых выходных сигналов) столбцы таблицы выходов. Классы (i+1) - совместимости получаются из классов i - совместимости путём их расщепления на классы (i+1) - совместимости. Для этого у каждого состояния, принадлежащего j - классу i - совместимости C_j(i), номера классов (индексы), в которые автомат переходит под воздействием каждой входной буквы. Если номер класса не определён, то ставится специальный символ, например, прочерк. Индексы классов, в которые переходит автомат под действием входного сигнала, образуют отметку. Множество состояний с одинаковыми отметками в классе C_j(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