Прикладна теорія цифрових автоматів 3 Міністерство освіти і науки України ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ Кафедра комп’ютерних інтелектуальних систем та мереж Курсове проектування з дисципліни „Прикладна теорія цифрових автоматів” Виконав: студент гр. Одеса 2002 1.ВИБІР ВАРІАНТА ЗАВДАННЯ Граф-схеми алгоритмів обираються кожним студентом в індивідуальному порядку. Вона складається з чотирьох блоків: E, F, G, H. Студенти обирають граф-схему із п’яти блоків з номерами 0...4 на підставі чисел А, В, С та (А+В+С) за наступними правилами: - блок "Е" – схема під номером (А) mod 5 = 27 mod 5 = 2; - блок "F" – схема під номером (В) mod 5 = 6 mod 5 = 1; - блок "G" – схема під номером (С) mod 5 = 13 mod 5 = 3; - блок "H" – схема під номером (А+В+С) mod 5 = 46 mod 5 = 1. Блоки E, F, G, H з’єднуються між собою згідно зі структурною схемою графа, яка показана на рис. 10 у методичних вказівках. Розташування обирається з використанням номера групи. Тип тригера знаходимо по таблиці на підставі числа (А) mod 3 = 27 mod 3 = 0. (A)mod 3 ТИПТРИГЕРА 0 Т D 1 D JK 2 JK T автомат Мілі Мура Табл.1 З табл.1 отримуємо T-тригер для автомата Мілі та D-тригер для Мура. Серія інтегральних мікросхем для побудови принципових схем синтезованих автоматів для мого варіанта завдання – КР1533. Після відповідної розмітки будуємо граф-схему для обоіх автоматів: 2. ОСНОВНА ЧАСТИНА 2. 1. Структурний синтез автомата Мура 2.1.1. Кодування станів Кодування станів буде проводитися за таким алгоритмом: 1. Кожному стану автомата аm (m = 1,2,...,M) ставиться у відповідність ціле число Nm , рівне числу переходів у стан аm (Nm дорівнює числу появ аm у поле таблиці ). 2. Числа N1 , N2 , ..., Nm упорядковуються по убуванні. 3. Стан аs з найбільшим Ns кодується кодом: де R-кількість елементів пам'яті. 4. Наступні R станів згідно списку пункту 2 кодуються кодами, що містять тільки одну 1:00 ... 01, 00 ... 10, ... , 01 ... 00, 10 ... 00. 5. Для станів, що залишилися, знову в порядку списку п.2. використовують коди з двома одиницями, потім із трьома і так далі поки не будуть закодовані всі стани. У результаті виходить таке кодування, при якому чим більше мається переходів у деякий стан, тим менше одиниць у його коді. Вираження для функцій збудження будуть простіше для D-тригерів, тому що функції порушення однозначно визначаються кодом стану переходу. Статистика: a1 2стана a2 1стан a3 2стана a4 1стан a5 2стана a6 1стан a7 1стан a8 2стана a9 2стана a10 1стан a11 2стана a12 1стан a13 1стан a14 2стана a15 2стана a16 2стана a17 2стана a18 2стана a19 1стан a20 2стана a21 2стана a22 2стана a23 1стан a24 2стана a25 3стана Результати кодування: a1 00011 a2 10011 a3 00110 a4 10101 a5 00101 a6 11001 a7 01011 a8 01100 a9 01010 a10 01101 a11 01001 a12 00111 a13 01110 a14 11000 a15 10100 a16 10010 a17 10001 a18 10000 a19 10110 a20 01000 a21 00100 a22 00010 a23 11010 a24 00001 a25 00000 Табл.2. Таблиця переходів D-тригера Am Kam As(y) X Kas D1D2D3D4D5 a13 a17 a1(-) 1 1 00011 D4D5 D4D5 a1 a2(y2y4) 1 10011 D1 D4D5 a2 a18 a3(y7) 1 X5 00110 D3D4 D3D4 a3 a4(y1y9) NX1 10101 D1 D3 D5 a4 a14 a5(y1y8) 1 X2 00101 D3 D5 D3 D5 a5 a6(y4) X4 11001 D1D2 D5 a6 a7(y4y5) 1 01011 D2 D4D5 a7 a15 a8(y2y4) 1 1 01100 D2D3 D2D3 a8 a22 a9(y7) 1 X5 01010 D2 D4 D2 D4 a9 a10(y1y9) NX1 01101 D2D3 D5 a10 a16 a11(y1y8) 1 X2 01001 D2 D5 D2 D5 a11 a12(y4) X4 00111 D3D4D5 a12 a13(y4y5) 1 01110 D2D3D4 a3 a18 a14(y8) X1 NX5NX6 11000 D1D2 D1D2 a5 a20 a15(y3y10) NX4NX3 X4NX3 10100 D1 D3 D1 D3 a9 a22 a16(y8) X1 NX5NX6 10010 D1 D4 D1 D4 a11 a24 a17(y3y10) NX4NX3 X4NX3 10001 D1 D5 D1 D5 a21 a20 a18(y3y6) 1 NX4NX1 10000 D1 D1 a18 a19(y3) NX5X6 10110 D1 D3D4 a19 a14 a20(y5y9) 1 NX2 01000 D2 D2 a20 a20 a21(y6) X4X3 NX4X1 00100 D3 D3 a25 a24 a22(y3y6) 1 NX4NX1 00010 D4 D4 a22 a23(y3) NX5X6 11010 D1D2 D4 a23 a16 a24(y5y9) 1 NX2 00001 D5 D5 a24 a24 a11 a25(y6) X4X3 NX4X1 NX4 X3 00000 2. 1 .2. Функції збудження тригерів та вихідних сигналів Введемо слідуючі позначення: Б= a20NХ4NХ1 Х=a3X1 В= a14NХ2 Ц=a18NX5NX6 Г= a20Х4Х3 Ч=a5NX4NX3 Д=a20NХ4Х1 Ш=a20X4NX3 Е=a18X5 Э=a9X1 Ж=a3NX1 Ю=a22NX5NX6 З= a24NХ4NХ1Я=a11NX4NX3 И=a14X2 Щ=a24X4NX3 К=a5X4 Ь=a18NX5X6 Л= a16NХ2Ы=a22NX5X6 П=a22X5 Р=a9NX1 Т=a16X2 У=a11X4 Виписуємо з таблиці вирази для тригерів: D1=a1+Ж+К+Ы+Х+Ц+Ч+Ш+Э+Ю+Я+Щ+a21+Б+Ь D2=К+a6+a7+a15+a8+П+Р+a10+Т+Х+Ц+а12+a19+В+Ы D3=a2+Е+Ж+a4+И+a7+a15+Р+У+a12+Ч+Ш+Г+Д+Ь D4= a13+a17+a1+a2+Е+a6+a8+П+У+a12+Э+Ю+Ь+a25+З+Ы D5=a13+a17+a1+Ж+a4+И+К+a6+Р+a10+Т+У+Я+Щ+a23+Л Формуємо функції виходів автомата: Y1=a4+a5+a10+a11 Y2=a2+a8 Y3=a15+a17+a18+a19+a22+a23 Y4=a2+a6+a7+a8+a12+a13 Y5=a7+a13+a20+a24 Y6=a18+a21+a22+a25 Y7=a3+a9 Y8=a5+a11+a14+a16 Y9=a4+a10+a20+a24 Y10=a15+a17 2. 1 .3. Переведеня у базис: D1=a1+Ж+К+Ы+Х+Ц+Ч+Ш+Э+Ю+Я+Щ+a21+Б+Ь= =Na1∙NЖ∙NК∙NЫ∙NХ∙NЦ∙NЧ∙NШ+NЭ∙NЮ∙NЯ∙NЩ∙Na21∙NБ∙NЬ D2=К+a6+a7+a15+a8+П+Р+a10+Т+Х+Ц+а12+a19+В+Ы= =NК∙Na6∙Na7∙Na15∙Na8∙NП∙NР∙Na10+NТ∙NХ∙NЦ∙Nа12∙Na19∙NВ∙NЫ D3= a2+Е+Ж+a4+И+a7+a15+Р+У+a12+Ч+Ш+Г+Д+Ь= =Na2∙NЕ∙NЖ∙Na4∙NИ∙Na7∙Na15∙NР+NУ∙Na12∙NЧ∙NШ∙NГ∙NД∙NЬ D4= a13+a17+a1+a2+Е+a6+a8+П+У+a12+Э+Ю+Ь+a25+З+Ы =Na13∙Na17∙Na1∙Na2∙NЕ∙Na6∙Na8∙NП+NУ∙Na12∙NЭ∙NЮ∙NЬ∙Na25∙NЗ∙NЫ D5= a13+a17+a1+Ж+a4+И+К+a6+Р+a10+Т+У+Я+Щ+a23+Л= =Na13∙Na17∙Na1∙NЖ∙Na4∙NИ∙NК∙Na6+NР∙Na10∙NТ∙NУ∙NЯ∙NЩ∙Na23∙NЛ Y1=a4+a5+a10+a11=Na4∙Na5∙Na10∙Na11 Y2=a2+a8= Na2∙Na8 Y3=a15+a17+a18+a19+a22+a23= Na15∙Na17∙Na18∙Na19∙Na22∙Na23 Y4=a2+a6+a7+a8+a12+a13= Na2∙Na6∙Na7∙Na8∙Na12∙Na13 Y5=a7+a13+a20+a24= Na7∙Na13∙Na20∙Na24 Y6=a18+a21+a22+a25= Na18∙Na21∙Na22∙Na25 Y7=a3+a9= Na3∙Na9 Y8=a5+a11+a14+a16= Na5∙Na11∙Na14∙Na16 Y9=a4+a10+a20+a24= Na4∙Na10∙Na20∙Na24 Y10=a15+a17= Na15∙Na17 Ми отримали усі необхідні вирази для принципової схеми. Будуємо її, користуючись формулами для тригерів та вихідними станами. 2.2. Структурний синтез автомата Мілі 2. 2. 1. Кодування станів Аналіз канонічного методу структурного синтезу автомата показує, що різні варіанти кодування станів автомата приводять до різних виражень функцій збудження пам'яті і функцій виходів, у результаті чого складність комбінаційної схеми істотно залежить від обраного кодування. Мы повинні кодувати стани автомату з допомогою евристичного алгоритму кодування, тому що у мене Т-тригер. Даний алгоритм мінімізує сумарне число переключень елементів пам'яті на всіх переходах автомата і використовується для кодування станів автомата при синтезі на базі T, RS, JK-тригерів. Для даних типів тригерів (на відміну від D-тригерів) на кожнім переході, де тригер змінює своє значення на протилежне, одна з функцій збудження обов'язково дорівнює 1. Зменшення числа переключень тригерів приводить до зменшення кількості одиниць відповідних функцій збудження, що при відсутності мінімізації однозначно приводить до спрощення комбінаційної схеми автомата. Будую матрицю |T|, яка складається із всіх пар номерів (i, j), для яких P(i, j)  0, ij. Для кожної пари вказуємо її вагу. ║T║ = i │ j │ P(i,j) 1 │ 2 │ 1 1 │ 11 │ 1 1 │ 12 │ 1 1 │ 21 │ 1 2 │ 3 │ 1 3 │ 4 │ 1 3 │ 13 │ 1 3 │ 15 │ 1 4 │ 5 │ 1 5 │ 6 │ 1 5 │ 7 │ 1 5 │ 13 │ 1 5 │ 18 │ 1 6 │ 7 │ 1 7 │ 8 │ 1 7 │ 17 │ 1 8 │ 9 │ 1 9 │ 10 │ 1 9 │ 14 │ 1 9 │ 19 │ 1 10 │ 11 │ 1 11 │ 12 │ 1 11 │ 14 │ 1 11 │ 22 │ 1 13 │ 15 │ 1 13 │ 17 │ 1 14 │ 19 │ 1 14 │ 21 │ 1 15 │ 16 │ 1 15 │ 17 │ 1 15 │ 18 │ 1 16 │ 17 │ 1 17 │ 18 │ 2 19 │ 20 │ 1 19 │ 21 │ 1 19 │ 22 │ 1 20 │ 21 │ 1 21 │ 22 │ 2 Підраховуємо вагу всіх компонентів всіх пар P(1) = 4 P(2) = 2 P(3) = 4 P(4) = 2 P(5) = 5 P(6) = 2 P(7) = 4 P(8) = 2 P(9) = 4 P(10) = 2 P(11) = 5 P(12) = 2 P(13) = 4 P(14) = 4 P(15) = 5 P(16) = 2 P(17) = 5 P(18) = 3 P(19) = 5 P(20) = 2 P(21) = 5 P(22) = 3 Далі згідно правил алгоритму будуємо матрицю М i │ j │ P(i,j) 17 │ 18 │ 2 15 │ 17 │ 1 3 │ 15 │ 1 7 │ 17 │ 1 5 │ 7 │ 1 5 │ 13 │ 1 13 │ 15 │ 1 13 │ 17 │ 1 3 │ 13 │ 1 5 │ 18 │ 1 15 │ 18 │ 1 4 │ 5 │ 1 5 │ 6 │ 1 15 │ 16 │ 1 16 │ 17 │ 1 2 │ 3 │ 1 1 │ 2 │ 1 1 │ 11 │ 1 1 │ 21 │ 1 21 │ 22 │ 2 19 │ 21 │ 1 9 │ 19 │ 1 11 │ 14 │ 1 14 │ 19 │ 1 14 │ 21 │ 1 9 │ 14 │ 1 11 │ 22 │ 1 19 │ 22 │ 1 10 │ 11 │ 1 11 │ 12 │ 1 19 │ 20 │ 1 20 │ 21 │ 1 1 │ 12 │ 1 3 │ 4 │ 1 6 │ 7 │ 1 7 │ 8 │ 1 8 │ 9 │ 1 9 │ 10 │ 1 Визначемо розрядність кода для кодування станів автомата R = ] log2 N [ = ] log2 22 [ = 5 Результати кодування: b1 01011 b2 01111 b3 00111 b4 01101 b5 00101 b6 01100 b7 00100 b8 10100 b9 10000 b10 11000 b11 11010 b12 01010 b13 00110 b14 11001 b15 00011 b16 00010 b17 00000 b18 00001 b19 10001 b20 10101 b21 10011 b22 10010 Підрахунок ефективності кодування: Кількість перемикань тригерів: W = E P(i,j)*d(i,j) = P(1,2)*d(1,2) + P(1,11)*d(1,11) + P(1,12)*d(1,12) + P(1,21)*d(1,21) + P(2,3)*d(2,3) + P(3,4)*d(3,4) + P(3,13)*d(3,13) + P(3,15)*d(3,15) + P(4,5)*d(4,5) + P(5,6)*d(5,6) + P(5,7)*d(5,7) + P(5,13)*d(5,13) + P(5,18)*d(5,18) + P(6,7)*d(6,7) + P(7,8)*d(7,8) + P(7,17)*d(7,17) + P(8,9)*d(8,9) + P(9,10)*d(9,10) + P(9,14)*d(9,14) + P(9,19)*d(9,19) + P(10,11)*d(10,11) + P(11,12)*d(11,12) + P(11,14)*d(11,14) + P(11,22)*d(11,22) + P(13,15)*d(13,15) + P(13,17)*d(13,17) + P(14,19)*d(14,19) + P(14,21)*d(14,21) + P(15,16)*d(15,16) + P(15,17)*d(15,17) + P(15,18)*d(15,18) + P(16,17)*d(16,17) + P(17,18)*d(17,18) + P(19,20)*d(19,20) + P(19,21)*d(19,21) + P(19,22)*d(19,22) + P(20,21)*d(20,21) + P(21,22)*d(21,22) = 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*2 + 1*1 + 1*2 + 1*1 + 2*1 + 1*2 + 1*1 + 1*2 + 1*1 + 2*1 = 52 Мінімально можлива кількість перемикань тригерів Wmin = E P(i,j) = 40 Коефіціент ефективності кодування: 1.30 Табл.3. Таблиця переходів Т-тригера Am Kam As Kas X Y ФЗ b1 01011 b2 01111 1 Y2Y4 T3 b2 01111 b3 00111 1 Y7 T2 b3 00111 b4 b13 01101 00110 NX1 X1 Y1Y9 Y8 T2 T4 T5 b4 01101 b5 00101 1 Y1Y8 T2 b5 00101 b6 b7 b18 01100 00100 00001 X4 NX4NX3 NX4X3 Y4 Y3Y10 Y6 T2 T5 T5 T3 b6 01100 b7 00100 1 Y4Y5 T2 b7 00100 b8 10100 1 Y2Y4 T1 b8 10100 b9 10000 1 Y7 T3 b9 10000 b10 b14 11000 11001 NX1 X1 Y1Y9 Y8 T2 T2 T5 b10 11000 b11 11010 1 Y1Y8 T4 b11 11010 b12 b1 b22 01010 01011 10010 X4 NX4NX3 NX4X3 Y4 Y3Y10 Y6 T1 T1 T5 T2 b12 01010 b1 01011 1 Y4Y5 T5 b13 00110 b5 b17 00101 00000 X2 NX2 Y1Y8 Y5Y9 T4T5 T3 T4 b14 11001 b11 b21 11010 10011 X2 NX2 Y3Y10 Y6 T4T5 T2 T4 b15 00011 b3 b13 b16 00111 00110 00010 X5 NX5NX6 NX5X6 Y7 Y8 Y3 T3 T3 T5 T5 b16 00010 b17 00000 1 Y5Y9 T4 b17 00000 b7 b18 b18 b15 00100 00001 00001 00011 X4NX3 X4X3 NX4X1 NX4NX1 Y3Y10 Y6 Y6 Y3Y6 T3 T5 T5 T4T5 2.2.2. Функції збудження тригерів та вихідних сигналів Введемо слідуючі позначення: A=b3NX1 П=b21Х4NX3 Б=b5X4 Р=b5NX4Х3 H=b9X1С=В15Х5 Г=b11X4 Т=b17Х4NX3 Д=b13X2 У= b19NX5X6 Е=b13NX2 Ф= b21NX4NX1 Ж=b14X2 Х= b3Х1 З=b14NX2 Ц= b5NX4NX3 И=b15NX5NX6 Ч= b11NX4NX3 К=b17NX4NX1 Ш= b15NX5X6 Л=b9NX1 Щ= b17X4X3 М=b11NX4X3 Э= b17NX4X1 O= b19NX5NX6 Ю= b21X4X3 Я= b21NX4X1 В=В19Х5 Виписуємо з таблиці вирази для тригерів: T1 =b7+Г+Ч+П Т2 =b2+А+b4+Б+b6+Л+Н+М+З+О+П Т3 =b1+Р+b8+Е+С+И+Т+У+b20 Т4 =А+b10+Д+Е+Ж+З+b16+К+b18+b20+Ф+b22 Т5 =Х+Б+Ц+H+Ч+b12+Д+Ж+И+Ш+Щ+Э+K+Ю+Я+b22 Формуємо функції виходів автомата: Y1=А+b4+Л+b10+Д Y2=b1+b7 Y3=Ц+Ч+Ж+Ш+Т+К+b18+У+П+Ф+b22 Y4=b1+Б+b6+b7+Г+b12 Y5=b6+b12+Е+b16+b20 Y6=М+З+Щ+Э+К+b18+Ю+Я+Ф+b22 Y7=b2+b8+С+В Y8=Х+b4+Н+b10+Д+И+О Y9=А+Л+Е+b16+b20 Y10=Ц+Ч+Ж+Т+П 2.2.3. Переведеня у базис: T1 =b7+Г+Ч+П= Nb7∙NГ∙NЧ∙NП Т2 =b2+А+b4+Б+b6+Л+Н+М+З+О+П= =Nb2∙NА∙Nb4∙NБ∙Nb6∙NЛ∙NН∙NМ+NЗ∙NО∙NП Т3 =b1+Р+b8+Е+С+И+Т+У+b20= =Nb1∙NР∙Nb8∙NЕ∙NС∙NИ∙NТ∙NУ+b20 Т4 =А+b10+Д+Е+Ж+З+b16+К+b18+b20+Ф+b22= =NА∙Nb10∙NД∙NЕ∙NЖ∙NЗ∙Nb16∙NК+Nb18∙Nb20∙NФ∙Nb22 Т5 =Х+Б+Ц+H+Ч+b12+Д+Ж+И+Ш+Щ+Э+K+Ю+Я+b22= =NХ∙NБ∙NЦ∙NH∙NЧ∙Nb12∙NД∙NЖ+NИ∙NШ∙NЩ∙NЭ∙NK∙NЮ∙NЯ∙Nb22 Y1=А+b4+Л+b10+Д= NА∙Nb4∙NЛ∙Nb10∙NД Y2=b1+b7= Nb1∙Nb7 Y3=Ц+Ч+Ж+Ш+Т+К+b18+У+П+Ф+b22=NЦ∙NЧ∙NЖ∙NШ∙NТ∙NК∙Nb18∙NУ+ +NП∙NФ∙Nb22 Y4=b1+Б+b6+b7+Г+b12=Nb1∙NБ∙Nb6∙Nb7∙NГ∙Nb12 Y5=b6+b12+Е+b16+b20= Nb6∙Nb12∙NЕ∙Nb16∙Nb20 Y6=М+З+Щ+Э+К+b18+Ю+Я+Ф+b22= NМ∙NЗ∙NЩ∙NЭ∙NК∙Nb18∙NЮ∙NЯ+ +NФ∙Nb22 Y7=b2+b8+С+В= Nb2∙Nb8∙NС∙NВ Y8=Х+b4+Н+b10+Д+И+О= NХ∙Nb4∙NН∙Nb10∙NД∙NИ∙NО Y9=А+Л+Е+b16+b20= NА∙NЛ∙NЕ∙Nb16∙Nb20 Y10=Ц+Ч+Ж+Т+П= NЦ∙NЧ∙NЖ∙NТ∙NП Ми отримали усі необхідні вирази для принципової схеми. Будуємо її, користуючись формулами для тригерів та вихідними станами. Висновок В ході проекту ми отримали комбінаційну схему булевої функції в заданому базисі та побудували принципову схему керуючого автомата Мура. Синтез автомата був виконаний з урахуванням серії КР 555, тому може бути зроблений та опробований в реальному житті. В цілому курсова робота довела свою важливість у закріпленні отриманих знань та набутті низки звичок щодо проектування цифрових автоматів. Перелік використаної літератури 1. Методичні вказівки до курсової роботи по дисципліні “Прикладна теорія цифрових автоматів”. Одеса. ОГПУ. 1998р. 2. Мікросхеми серії 1533(555). Стислі теоретичні дані. Одеса. Центр НТТМ ОГПУ. 1975г. 3.ГОСТ 2.708-81 ЄСКД. Правила виконання електричних схем цифрової обчислювальної техніки. 4. ГОСТ 2.743-82. ЄСКД. Умовні графічні позначення в схемах. Елементи цифрової техніки.