Главная Финансы деньги и налоги Философия Физика и энергетика Управление Схемотехника Стратегический менеджмент Статистика Соцобеспечение Семейное право Программирование компьютеры и кибернетика Охрана окружающей среды экология Основы права Медицина Криминалистика и криминология Коммуникации и связь Кибернетика Качество упр-е качеством КСЕ Информатика ВТ телекоммуникации Журналистика Государство и право Биографии Банковское дело Карта сайта	Рефераты. Построение кодопреобразователя	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 -следующий момент дискретного автоматного времени.

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

 

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

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

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

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

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

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20