Математичекие основи теорії систем: аналіз сигнального графа і синтез комбінаційних схем

Министерство спеціального і помилки вищого образования.

Хабаровський державний технічний университет.

Кафедра «Автоматика і системотехника».

Курсової проект.

По предмета: Математичні основи теорії систем.

|Выполнил студент грн. УИТС-21у: |Д.І. Хоменко | |Перевірив: |В.В. Воронін |.

р. Хабаровск.

2003 г.

ЗАДАНИЕ.

Курсова робота складається з 3-х розділів, у кожному у тому числі розглядається окремий параграф дисципліни «Математичні основи теорії систем».

У першому його розділі даної курсової роботи потрібно, маючи схему системи автоматичного управління можливість перейти до сигнальному графу, визначити її структурні характеристики і проаналізувати з допомогою формули Мезона.

У другому розділі необхідно розглянути логічні функції, методи їхнього завдання й синтез комбінаційних схем.

У третьому розділі необхідно синтезувати автомат з пам’яттю з урахуванням змістовного описи алгоритму його работы.

РЕФЕРАТ.

Курсова робота містить пояснювальну записку що складається із трьох розділів на 38 аркушах формату А4, що включає 6 малюнків, 2 схеми, 14 таблиць і трьох літературних источника.

Об'єктом дослідження є система автоматичного управління і логічне пристрій, у разі семисегментный элемент.

Мета праці полягає у тому аби практично теоретичний матеріал курсу лекцій «Математичні основи теорії систем» і придбання навичок з аналізу систем і синтезу схем.

Ключове слово: структурна схема, сигнальний граф, шлях, конур, САУ, синтез схем, кінцевий автомат, логічна функція, таблиця істинності, мінімізація, карти Карно, невизначені коефіцієнти, первинні импликаты, минитермы, функціональна схема, триггер.

ЗАВДАННЯ 2.

РЕФЕРАТ 3.

Содержание 4.

Задание 1. Аналіз сигнальних графів. 7.

1.1 Вибір варіанта завдання 7.

1.2 Перетворення структурної схеми до сигнальному графу 7.

1.2 Перетворення структурної схеми до сигнальному графу 8.

1.4 Матриця инцидентности 9.

1.5 Побудова бінарних матриць шляхів виходу для заданих контрольних точок. 10.

1.6 Бінарна матриця контурів. 12.

1.7 Матриця торкання контурів 12.

1. 8 Матриця торкання колій та контурів 13.

1.9 Формула Мэзона для заданого сигнального графа 13.

Задание 2. Синтез комбінаційних схем. 16.

2.1 Визначення поставленого завдання 16.

2.2 Упорядкування логічних функцій 19 2.2.1 Дизъюнктивная досконала нормальна форма 19 2.2.2 Конъюнктивная досконала нормальна форма 20.

2.3 Мінімізація булевых функцій 20 2.3.1 Приклад мінімізації методом невизначених коефіцієнтів 21 2.3.2 Приклад мінімізації методом Квайна-Мак-Класки. 22 2.3.3 Приклад мінімізації картами Карно 25.

2.4 Спільна мінімізація всіх функцій 26.

2.5 Запис МДНФ в заданому базисі 27.

3. СИНТЕЗ АВТОМАТА З ПАМ’ЯТТЮ 29.

3.1 Аналіз технічного завдання 29.

3.2 Формальне опис абстрактного автомата 29.

3.3 Кодування вхідних і вихідних символів станів 31.

3.4 Узагальнена функціональна схема структурного автомата 32.

3.5 Канонічна система логічних рівнянь 33.

3.6 Мінімізація логічних функцій 35.

3.7 Побудова комбінаційної схеми автомата з пам’яттю 35.

ЗАКЛЮЧЕНИЕ

36.

Приложение 1. 37.

Приложение 2 38.

Задание 1. Аналіз сигнальних графов.

1 Вибір варіанта задания.

З літер, їхнім виокремленням прізвище, ім'я і по батькові одержимо три безлічі А, У і З символів російського алфавіту. Хоменко А={Х, Про, М, Є, М, До} Дмитро B={Д, М, І, Т, Р, Й} C={И, Р, Про, Р, Є, У, Ч}.

Провівши відповідні операції над множинами одержимо їх потужності. З таблиці можливих потужностей методичного вказівки вибираються типи відповідних отриманих результатів типи сполук елементів у системі автоматичного управління. (A (B (=({ Х, Про, М, Є, М, До, Д, І, Т, Р, Й }(=11 ((A (B)(С (=({Е, І, Про, Р}(=4 (CA (=({И, Р, Р, У, Ч}(=5 (A (B (=(U A (B (=33−11=22.

Із одержаних результатам побудуємо схему автоматичного управління системой.

1.2 Перетворення структурної схеми до сигнальному графу.

Граф проходження сигналу G=, де Х — безліч вершин, (- безліч дуг, має такі особенности.

1. Кожній вершині графа xi (X ставлять у відповідність одна змінна структурної схеми (позначення змінних сигналів наведено малюнку 1.1).

2. Кожній дузі (xi, xj)(X поставлено відповідність передатна функція однієї з блоків структурної схемы.

3. Якщо з вершини виходить кілька дуг, то тут для них вхідні величина загальна. Це усуває в графі точки разветвления.

4. Якщо вершину входить кілька ребер, то відповідна цією вершиною змінна дорівнює сумі вхідних сигналів. Це непотрібним використання у графі сумматоров.

З огляду на перелічені особливості переходу від структурної схеми до сигнальному графу, перейдемо від схеми рис. 1.1 до відповідного сигнальному графу (див. рис. 1.2).

Вершини відзначені сірим кольором — це задані контрольні точки. 1.3 Матриця смежности.

Сволоком суміжності графа G називається матриця R=[rij] розміром nxn, де n — число вершин графа, в которой.

[pic] |1 |1 |1 |1 |1 |1 |1 |1 |1 | |2 |1 |1 |1 |1 |1 |1 |1 |1 | |3 |1 |1 |1 |1 |1 |1 |1 |1 | |4 |1 |1 |1 |1 |1 |1 |1 |1 | |5 |1 |1 |1 |1 |1 |1 |1 |1 | |6 |1 |1 |1 |1 |1 |1 |1 |1 | |7 |1 |1 |1 |1 |1 |1 |1 |0 | |8 |1 |1 |1 |1 |1 |1 |0 |1 |.

1. 8 Матриця торкання колій та контуров.

Бінарна матриця контурів Cl=((cij ((розміру lxk, де l — число шляхів для заданого виходу, будується з такого правилу:

[pic].

Для 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 Формула Мэзона для заданого сигнального графа.

Використовуючи універсальну топологічну формулу, що носить ім'я Мэзона, можна отримати роботу передачу між будь-якими двома вершинами. Формула має наступний вид:

[pic] де [pic]- передача k-го шляху між вершинами j і r; [pic](- визначник графа. Він характеризує контурну частина графа і має наступний вид:

[pic] де, L — безліч індексів контурів, L2 — безліч пар індексів не що стосуються контурів, L3 — безліч трійок індексів які стосуються контурів, Ki — передача i-го контуру, [pic] - мінор шляху, це визначник подграфа, отриманого видаленням з повного графа вершин і дуг, їхнім виокремленням шлях [pic]. (=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 [pic] [pic] [pic].

Для x4 [pic] [pic] [pic] [pic] [pic].

Для y [pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic].

[pic].

[pic].

[pic].

[pic].

[pic].

Для х13.

[pic] [pic] [pic] [pic] [pic] [pic] [pic] [pic].

[pic].

[pic].

[pic].

[pic].

[pic].

Задание 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 |Нульова група |0000+ |Нульова група |0−00 | |Перша група |0100+ |Перша група |-100, -011 | |Друга ж група |1100, 1010, 0011 |Друга ж група |11−0, 1−10, 101- | |Третю групу |1110, 1011 | | |.

Розстановка міток. Інші етапи потрібні, щоб відкинути деякі первинні импликанты. На цьому етапі складається таблиця, число рядків якої одно числу отриманих первинних импликант, число шпальт збігається з кількістю минитермов СДНФ. Якщо певний минитерм СДНФ входить яка — або з первинних импликант, то, на перетині відповідного шпальти і рядки ставиться мітка. У таблиці 2.2.2 наведемо результат розстановки меток:

Таблиця 2.2.2 |-100 |У | | | |11−0 |У | |У | |1−10 | |У |У | |101- | |У | |.

Вибір мінімального покриття. Досліджується результуюча таблиця. Вибирається така сукупність первинних импликант, яка иссключает мітки переважають у всіх шпальтах (по крайнього заходу за однією у кожному стовпці). При кількох можливі варіанти такого вибору віддається перевагу варіанту покриття з мінімальним сумарним числом літер у простих импликантах, їхнім виокремленням покрытие.

З урахуванням істотних импликант одержимо дві МДНФ з цією функції має вид:

1. pic].

2. [pic].

Кількість літер складових прості імплікації у кожному варіанті однаково. У другому варіанті одне заперечення менше, тому беремо його з искомое:

[pic].

2.3.3 Приклад мінімізації картами Карно.

Він для мінімізації функції в коді Грея. У кожну комірку записується значення функції цьому наборі. Потім виділяються групи осередків розміром 2a*2b, де a, b?[0,1,2…], у яких функція приймає значення «1». У кожну групу повинно входити максимальну кількість осередків. Таких груп має бути мінімум. Кожній групі буде відповідати конъюнктивный член розміром n-a-b. Для отримання МДНФ кожну групу треба переглядати в горизонтальному і вертикальному вимірах, з перебування таких змінних, які змінюють свого значення межах групи. Якщо змінна не змінює свого нульового значення, вона вписується в конъюнкцию з запереченням, а то й змінює свого одиничного значення, то вписується без заперечення. Якщо є розірвані групи, то карту Карно треба звернути в циліндр. На невизначених наборах слід доопределить нулем чи одиницею, в відповідність до обраній групою осередків. Кожна одинична осередок повинна бути включена хоча в одну группу.

Складемо карту Карно для функції У3 (малюнок 2.3.1).

| |x3x4 | |x1x2| |00 |01 |11 |10 | | |00|1 | |1 | | | |01|1 | | | | | |11|1 | | |1 | | |10| | |1 |1 |.

Рис. 2.3.1 Карта Карно для функції У3.

Таким чином, для функції У3 в МДНФ матиме наступний вид:

[pic].

2.4 Спільна мінімізація всіх функций.

Синтез схем з урахуванням окремо мінімізованих функцій є неоптимальним, з погляду кількості використовуваних елементів. Оскільки найімовірніше, є такі конъюнкции, які дублюють одне одного. Метою даного пункту є перебування цих конъюнкций.

І тому складемо карти Карно кожної функції з таблиці істинності (таблиця 2.1.1). Доопределим її заборонені набори (таблиця 2.1.1), та був згрупуємо осередки в такий спосіб, щоб такі групи було мінімальне кількість на даної карті і забезпечити максимальне збіг такі групи між картами інших функций.

Складемо карти Карно всім функцій таблиці істинності (таблиця 2.1.1).

|х1×2×3 | | | | |0 0 0 |s1 |s1 |s1 | |0 0 1 |s2 |s2 |s2 | |0 1 0 |s1 |s1 |s1 | |0 1 1 |s3 |s3 |s3 | |1 0 0 |s1 |s1 |s1 | |1 0 1 |s3 |s3 |s3 | |1 1 0 |s2 |s2 |s2 | |1 1 1 |s1 |s1 |s1 |.

Таблиця переходів — виходів представленій у таблиці 3.2.2 .

Таблиця 3.2.2 |P.S |s1 |s2 |s3 | |х1×2×3 | | | | |0 0 0 |у0 |у0 |у0 | |0 0 1 |у0 |у2 |у4 | |0 1 0 |у1 |у0 |у2 | |0 1 1 |у0 |у2 |у4 | |1 0 0 |у3 |у1 |у0 | |1 0 1 |у0 |у2 |у4 | |1 1 0 |у1 |у0 |у2 | |1 1 1 |у0 |у2 |у4 |.

А, щоб зберігати поточний стан потрібно n=[log?M] елементів пам’яті, де М — потужність алфавіту станів,? — число станів елементів пам’яті. Отже, необхідно log23=2 елементів памяти.

3.3 Кодування вхідних і вихідних символів состояний.

Кодування вхідних символів представлено в таблиці 3.3.1 .

Таблиця 3.3.1 |Х |х3[p|х2 |х1 | | |ic] | | | |х1 |0 |0 |0 | |х2 |0 |0 |1 | |х3 |0 |1 |0 | |х4 |0 |1 |1 | |х5 |1 |0 |0 | |х6 |1 |0 |1 | |х7 |1 |1 |0 | |х8 |1 |1 |1 |.

Кодування вихідних символів представлено в таблиці 3.3.2 .

Таблиця 3. 3.2 | |у1 |у2 |у3 | |у0 |1 |0 |1 | |у1 |0 |0 |0 | |у2 |1 |0 |0 | |у3 |1 |1 |1 | |у4 |1 |1 |0 |.

Кодування станів автомата представлено в таблиць 3.3.3.

Таблиця 3.3.3 |P.S |t1 |t2 | |s1 |0 |0 | |s2 |0 |1 | |s3 |1 |1 |.

Відповідно до таблицями 3.3.1 — 3.3.3 складаємо таблицю переходів — входів в кодированном виде.

Таблиця 3.3.4 |х3×2х1s1s2s3|00 |01 |11 | |000 |00 |01 |11 | |001 |00 |00 |00 | |010 |01 |01 |01 | |011 |00 |00 |00 | |100 |11 |11 |11 | |101 |00 |00 |00 | |110 |01 |01 |01 | |111 |00 |00 |00 |.

До того ж складемо кодовану таблицю переходів выходов.

Таблиця 3.4.5 |х3×2х1s1s2s|00 |01 |11 | |3 | | | | |000 |101 |101 |101 | |001 |101 |100 |110 | |010 |000 |101 |100 | |011 |101 |100 |110 | |100 |111 |000 |101 | |101 |101 |100 |110 | |110 |000 |101 |100 | |111 |101 |100 |110 |.

3.4 Узагальнена функціональна схема структурного автомата.

Побудуємо узагальнену функціональну схему структурного автомата з урахуванням заданого типу автомата і триггера (див. рис. 3.4.1) .

Рис. 3.4.1.

На малюнку 3.4.1 функціональна схема і двох блоків. Перший блок — блок пам’яті, що складається з двох елементів пам’яті (D — тригер, П1, П2). Другий блок — комбінаційна схема (КС1).

3.5 Канонічна система логічних уравнений.

З таблиці переходів виходів (табл. 3.4.5) можна було одержати СДНФ для у (виходів нашого автомата).

[pic].

[pic][pic].

[pic].

Перебування функцій порушення пам’яті (Ф1, Ф2) виробляється у відповідність до типом триггера. D — тригер має один вхід і тільки вихід, його зображення наведено на рис. 3.5.1 .

Рис. 3.2 D — триггер

Функція переходів даного автомата пам’яті приведено у таблиці 3.8. Якщо закодувати вхідні і вихідні символи D — триггера (табл. 3.9., 3.10), то кодированная таблиця переходів набуде вигляду таблиці 3.5.1.

Таблиця 3.5.1 |((|0 |1 | |0 |0 |0 | |1 |1 |1 |.

При побудові функцій порушення пам’яті автомата будують функцію входів елемента пам’яті. Цю функцію задають як таблиці. Функція входів структурного автомата пам’яті П приведено в таблиці 3.5.2 .

Таблиця 3.5.2 |tисх |Ф |tнов | |0 |0 |0 | |0 |1 |1 | |1 |0 |0 | |1 |1 |1 |.

Функція порушення автомата пам’яті, побудована відповідність до таблицями 3.12 і 3.7 представленій у таблиці 3.13 .

Таблиця 3.5.3 |х3×2х1t1t2 |00 |01 |11 | |000 |00 |01 |11 | |001 |00 |00 |00 | |010 |01 |01 |01 | |011 |00 |00 |00 | |100 |11 |11 |11 | |101 |00 |00 |10 | |110 |01 |01 |01 | |111 |00 |00 |10 |.

З цієї таблиці для одиничних значень функції Ф1 і Ф2 имеем:

[pic].

[pic].

3.6 Мінімізація логічних функций.

З допомогою програми Logic можна мінімізувати, отримані у минулому розділі логічні функції. У результаті вони приймуть вид:

[pic].

[pic].

3.7 Побудова комбінаційної схеми автомата з памятью.

Схема автомата з пам’яттю заснованої на D-триггере представленій у Додатку 2.

ЗАКЛЮЧЕНИЕ

.

У курсової роботу з дисципліни «Математичні основи теорії систем» було виконано два розділу, у якому закріплені теоретичні знання на теми: аналіз сигнального графа і синтез комбінаційних схем.

У першому його розділі досліджується сигнальний граф: перетворення структурної схеми до сигнальному графу, розрахунок передач графа. Для описи графа, використовувалися його структурні характеристики: матриця суміжності, матриця торкання колій та контурів, матриця инциденций, матриця шляхів, матриця контурів, матриця торкання контуров.

У другому розділі отримано деякі навички у сфері синтезу комбінаційних схем. Результатом зробленого стала комбінаційна схема управління світлодіодами семисегментного индикатора.

У третьому розділі необхідно синтезували автомат з пам’яттю з урахуванням змістовного описи алгоритму його работы.

Додаток 1.

Додаток 2.

———————————;

W1.

W2.

W4.

W3.

W5.

W6.

W7.

W8.

x.

x1.

x2.

x3.

x4.

x5.

x6.

x8.

x9.

x.

x10.

y.

x11.

x12.

x13.

x7.

Малюнок 1.1.1.

X.

x1.

x2.

x3.

x4.

x5.

x6.

x7.

Y.

x8.

x9.

x10.

x11.

x12.

x13.

КС1.

П2.

П1.

y7.

y6.

y5.

y4.

y3.

y2.

y1.

[pic].

х.

&.

[pic].

х2.

х1.

&.

[pic].

х2.

х1.

[pic].

х.

х3×2×1.

у1 у2 у3.

Ф1.

Ф2.

t1.

t2.

(.

(.

D.

w1.

w5.

w6.

w2.

w7.

w8.

w4.

w3.

u9.

u10.

u11.

u12.

u15.

u16.

u13.

u17.

u18.

u19.

u20.

u14.

Малюнок 1.2.1.