Mots (Математичекие основы теории систем: анализ сигнального графа и синтез комбинационных схем), страница 4
Описание файла
Документ из архива "Математичекие основы теории систем: анализ сигнального графа и синтез комбинационных схем", который расположен в категории "". Всё это находится в предмете "остальные рефераты" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "остальные рефераты" в общих файлах.
Онлайн просмотр документа "Mots"
Текст 4 страницы из документа "Mots"
где 
- передача k-го пути между вершинами j и r; 
- определитель графа. Он характеризует контурную часть графа и имеет следующий вид:
где, L – множество индексов контуров, L2 - множество пар индексов не касающихся контуров, L3 - множество троек индексов не касающихся контуров, Ki – передача i-го контура, 
- минор пути, это определитель подграфа, полученного удалением из полного графа вершин и дуг, образующих путь .
=1-К1-К2-К3-К4-К5-К6-К7-К8+К7К2+К7К3+К7К5+К7К6+К7К8=1- К1-К2-К3-К4-К5-К6-К7-К8+К7(К2+К3+К5+К6+К8)
К1=W1W3W4W5W6
K2=W3W4W7
K3=W1W3W4W8
K4=W2W3W4W6 W7
K5=W2W3W4W7
K6=W2W3W4W8
K7=W5W6
K8=W3W4
=1- W3W4(W1W5W6+ W7+ W1W8+ W2W6 W7+ W2W7+2W2W8+ 1)+ W5W6(W3W4(W7+ W1W5W6+ W2W7+ W2W8+1)-1)
Для x1
Для x4
Для y
Для х13
Задание 2. Синтез комбинационных схем.
2.1 Определение поставленной задачи
Устройство, работа которого может быть представлена на языке алгебры высказываний, принято называть логическим. Пусть такое устройство имеет n выходов и m входов. На каждый вход может быть подан произвольный символ конечного множества Х, называемого входным алфавитом. Совокупность входных символов, поданных на входы устройства, образует входное слово Рi в алфавите Х. На выходе устройства появляются выходные слова Qj, составленные из символов выходного алфавита Y. В силу конечности алфавитов X, Y и слов Pi, Qj (длина слова всегда равна m, а выходного слова - h) общее количество различных входных и выходных слов также конечно.
Элементарный такт работы устройства состоит в том, что при появлении на входе слова Рi устройство выдает на выходах комбинацию символов yi, образующих слово Qj. Если слово Qj определяется только входным словом на данном такте, то устройство называется конечным автоматом без памяти, или комбинационной схемой.
Алгоритм функционирования комбинационного устройства будет определен, если задать таблицу соответствия {Pi}->{Qj} для всех слов Pi. Если входной алфавит X состоит из K различных символов, в таблице соответствия будет Km строк. Так как символы входного и выходного алфавитов принимают только два значения (в данном случае «1» или «0»), то при синтезе и анализе логического устройства применяется булева алгебра.
Произвольные входной и выходной алфавиты могут быть приведены к автомату с двойным входом и выходом путем соответствующего кодирования. Однако этот автомат должен оперировать со словами входного и выходного алфавитов, длина которых больше длин соответствующих слов исходного алфавита.
Под синтезом комбинационной схемы подразумевается построение логической схемы проектируемого устройства в заданном базисе логических элементов. Исходным материалом к синтезу является словесное описание работы устройства.
Согласно заданию на курсовое проектирование было предложено закодировать исходный алфавит кодом Грея и использовать для синтеза конечного автомата базис {и, не}.
Код Грея является циклическим кодом, получается из двоично-десятичного кода по следующим правилам:
-
пусть gn…..g1g0 – кодовый набор в коде Грея с (n+1) разрядами.
-
bn…b1b0 – соответствующее двоичное число.
-
тогда разряд g0 получается из следующего выражения:
gi=bibi+1; 0in-1; gn=bn; где - символ операции сложения по модулю 2 (0+0=0, 0+1=1, 1+0=1, 1+1=0).
Закодируем входной алфавит в соответствии с этими правилами и с учетом значений yi составим таблицу истинности (см. таблицу 2.1.1).
Таблица 2.1.1
| Выходной символ | Сигнал (код) | y1 | y2 | y3 | y4 | y5 | y6 | y7 | ||||
| x4 | x3 | x2 | x1 | |||||||||
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 2 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 3 |
| 3 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 2 |
| 4 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 6 |
| 5 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 7 |
| 6 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 5 |
| 7 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 4 |
| 8 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 12 |
| 9 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 13 |
| 10 | 1 | 0 | 1 | 0 | * | * | * | * | * | * | * | 8 |
| 11 | 1 | 0 | 1 | 1 | * | * | * | * | * | * | * | 9 |
| 12 | 1 | 1 | 1 | 0 | * | * | * | * | * | * | * | 10 |
| 13 | 1 | 1 | 1 | 1 | * | * | * | * | * | * | * | 11 |
| 14 | 1 | 0 | 0 | 0 | * | * | * | * | * | * | * | 14 |
| 15 | 1 | 0 | 0 | 1 | * | * | * | * | * | * | * | 12 |
Если не удается заполнить все строки этой таблицы, то функция называется не полностью определенной, а наборы на которых она не определена, носят название запрещенных. В этом случае схема называется неполной. Доопределение функции производится произвольно.
2.2 Составление логических функций
Существует два способа записи логической функции по таблице истинности: запись дизъюнктивной совершенной нормальной формы (ДСНФ) и запись конъюнктивной совершенной нормальной формы (КСНФ). В первом случае образуют дизъюнкции, соответствующие входным наборам, на которых функция принимает значение «1», их объединяют знаками конъюнкции. Во втором случае организуют конъюнкции, соответствующие входным словам, на которых функция принимает значение «0», эти конъюнкции объединяют знаками дизъюнкции. Рассмотрим на примере функции у3.
2.2.1 Дизъюнктивная совершенная нормальная форма
Введем понятие логической степени, которою будем обозначать 
. Тогда, логическая степень будет определяться по формуле (2.1)
(2.1)
