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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Десятичные цифры	Входной код 4311	Выходной код 5311
0	0000000	000 0000
1	0001000	000 0001
2	0010000	000 0010
3	0011000	000 0011
4	0100000	000 0100
5	0101000	000 0101
6	1000000	000 1010
7	1001000	000 1011
8	1100000	000 1110
9	1101000	000 1111

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

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

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 -следующий момент дискретного автоматного времени.

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

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

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

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