Построение кодопреобразователя (стр. 2 из 8)
Элементы алгебры логики имеют следующие операции:
Конъюнкция(И, логическое умножение) - произведение двух высказываний Р и 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. Это значит, что если автомат перешёл в некоторое состояние х, то выйти из этого состояния может только под действием другого сигнала.