Реферат: Математичекие основы теории систем: анализ сигнального графа и синтез комбинационных схем
Для x1
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
Для x4
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 2 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
Для y
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 2 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 3 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 5 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 6 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
Для x13
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 3 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 5 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
| 6 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
1.9 Формула Мэзона для заданного сигнального графа
Используя универсальную топологическую формулу, носящую имя Мэзона, можно получить передачу между любыми двумя вершинами. Формула имеет следующий вид:
где 
-
передача k-го пути между вершинами j и r; 
D - определитель
графа. Он характеризует контурную часть графа и имеет следующий вид:
где, L – множество индексов контуров, L2 - множество пар индексов
не касающихся контуров, L3 - множество троек индексов
не касающихся контуров, Ki – передача i-го контура, 
- минор пути, это
определитель подграфа, полученного удалением из полного графа вершин и дуг,
образующих путь 
.
D=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
D=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»), то при синтезе и анализе логического устройства применяется булева алгебра.
Произвольные входной и выходной алфавиты могут быть приведены к автомату с двойным входом и выходом путем соответствующего кодирования. Однако этот автомат должен оперировать со словами входного и выходного алфавитов, длина которых больше длин соответствующих слов исходного алфавита.
Под синтезом комбинационной схемы подразумевается построение логической схемы проектируемого устройства в заданном базисе логических элементов. Исходным материалом к синтезу является словесное описание работы устройства.
Согласно заданию на курсовое проектирование было предложено закодировать исходный алфавит кодом Грея и использовать для синтеза конечного автомата базис {и, не}.
Код Грея является циклическим кодом, получается из двоично-десятичного кода по следующим правилам:
1. пусть gn…..g1g0 – кодовый набор в коде Грея с (n+1) разрядами.
2. bn…b1b0 – соответствующее двоичное число.
3. тогда разряд g0 получается из следующего выражения:
gi=biÅbi+1; 0£i£n-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 |
