РЕФЕРАТЫ ПО ТЕХНОЛОГИИРеферат: Прикладная теория цифровых автоматов1. ПОБУДОВА ОБ'ЄДНАНОЇ ГСА 1.1. Побудова ГСА По описах граф-схем, приведених в завданні до курсової роботи, побудуємо ГСА Г1-Г5 (мал. 1.1-1.5), додавши початкові і кінцеві вершини і замінивши кожний оператор Yi операторною вершиною, а кожну умову Xi - умовною. 1.2. Методика об'єднання ГСА У ГСА Г1-Г5 є однакові ділянки, тому побудова автоматів за ГСА Г1-Г5 приведе до невиправданих апаратурних витрат. Для досягнення оптимального результату скористаємося методикою С.І.Баранова, яка дозволяє мінімізувати число операторних і умовних вершин. Заздалегідь помітимо операторн( вершини в початкових ГСА, керуючись сл(дуючими правилами: 1) однакові вершини Yi в різних ГСА відмічаємо однаковими мітками Aj; 2) однакові вершини Yi в межах однієї ГСА відмічаємо різними мітками Aj; 3) у всіх ГСА початкову вершину помітимо як А0, а кінцеву - як Ak. На наступному етапі кожн(й ГСА поставимо у відповідність набір змінних Pn( {P1...Pq}, де q=]log2N[, N -к(льк(сть ГСА. Означувальною для ГСА Гn ми будемо називати кон`юнкцию Pn=p1e(...(pqn е({0,1}, причому p0=(р, p1=р. Об'єднана ГСА повинна задовольняти сл(дуючим вимогам: 1) якщо МК Ai входить хоча б в одну часткову ГСА, то вона входить і в об'єднану ГСА Г0, причому тільки один раз; 2) при підстановці набору значень (е1...en), на якому Pq=1 ГСА Г0 перетворюється в ГСА, рівносильну частков(й ГСА Гq. При об'єднанні ГСА виконаємо сл(дуючі етапи: -сформуємо часткові МСА М1 - М5, що відповідні ГСА Г1 - Г5; - сформуємо об'єднану МСА М0; - сформуємо системи дужкових формул переходу ГСА Г0; - сформуємо об'єднану ГСА Г0. 1.3. Об'єднання часткових ГСА Часткові МСА М1-М5 побудуємо по ГСА Г1-Г5 (мал.1.1) відповідно. Рядки МСА відмітимо всіма мітками Ai, що входять до ГСА, крім кінцевої Ak. ПОЧАТОК A0 1 0 X1 1 2 A1 3 0 4 X2 A2 1 5 A3 6 A4 7 A5 8 A6 9 A7 10 A8 К(НЕЦь Ak Мал.1.1. Часткова граф-схема алгоритму Г1 ПОЧАТОК A0 1 A1 2 A7 0 3 1 X3 4 5 A9 A6 6 7 A10 A12 8 9 A3 A22 10 A11 К(НЕЦЬ Ak Мал.1.2. Часткова граф-схема алгоритму Г2 ПОЧАТОК A0 1 A11 0 2 1 X1 3 4 A15 A16 6 5 1 X3 A12 0 7 8 A6 A13 К(НЕЦЬ Аk Мал.1.3. Часткова граф-схема алгоритму Г3 ПОЧАТОК A0 1 0 1 X1 2 A13 3 A9 4 A8 5 1 X2 6 0 A17 7 A6 8 A2 9 A18 К(НЕЦЬ Ak Мал.1.4. Часткова граф-схема алгоритму Г4 ПОЧАТОК A0 1 A1 2 A6 3 A19 4 0 1 X1 5 0 X2 1 6 A20 7 A17 8 A2 9 A21 К(НЕЦЬ Ak Мал.1.5. Часткова граф-схема алгортиму Г5 Стовпці МСА відмітимо всіма мітками Ai, що входять до ГСА, крім початкової A0. На перетині рядка Ai і стовпця Aj запишемо формулу переходу fij від оператора Ai до оператора Aj. Ця функція дор(вню( 1 для безумовного переходу або кон`юнкц(( логічних умов, відповідних виходам умовних вершин, через які проходить шлях з вершини з м(ткою Ai у вершину з м(ткою Aj. За методикою об'єднання закодуємо МСА таким чином: Таблиця 1.1 Кодування МСА МСА P1P2P3 М1 0 0 0 ((p1(p2(p3) М2 0 0 1 ((p1(p2p3) М3 0 1 0 ((p1p2(p3) М4 0 1 1 ((p1p2p3) М5 1 0 0 (p1(p2(p3) Частков( МСА М1-М5 наведен( в табл.1.2-1.6 Таблиця 1.2 Часткова МСА М1 A1 A2 A3 A4 A5 A6 A7 A8 Ak A0 (x1 (x1(x2 x1x2 A1 1 A2 1 A3 1 A4 1 A5 1 A6 1 A7 1 A8 1 Таблиця 1.3 Часткова МСА М2 A1 A3 A6 A7 A9 A10 A11 A12 A22 Ak A0 1 A1 1 A3 1 A6 1 A7 x3 (x3 A9 1 A10 1 A11 1 A12 1 A22 1 Таблиця 1.4 Часткова МСА М3 A6 A12 A13 A14 A15 A16 Ak A0 1 A6 1 A12 1 A13 1 A14 (x1 x1 A15 x3 (x3 A16 1 Таблиця 1.5 Часткова МСА М4 A2 A6 A8 A9 A13 A17 A18 Ak A0 (x1 x1 A2 1 A6 1 A8 x2 (x2 A9 1 A13 1 A17 1 A18 1 Таблиця 1.6 Часткова МСА М5 A1 A2 A6 A17 A19 A20 A21 Ak A0 1 A1 1 A2 1 A6 1 A17 1 A19 x1(x2 x1x2 (x1 A20 1 A21 1 На наступному етапі побудуємо об'єднану МСА М0, в як(й рядки відмічені всіма мітками Аi, крім Аk, а стовпці - всіма, крім А0. На перетині рядка Аi і стовпця Аj запишемо формулу переходу, яка формується таким чином: Fij=P1fij1+...+Pnfijn (n=1...N). Де fijn- формула переходу з вершини Аi у вершину Аj для n-о( ГСА. Наприклад, формула переходу А0(А1 буде мати вигляд F0,1=(x1(p1(p2(p3+ (p1(p2p3+ +p1(p2(p3. У результаті ми отримаємо об'єднану МСА М0 (табл.1.7). Ми маємо можливість мінімізувати формули переходу таким чином: розглядаючи ГСА Г0 як ГСА Гn, ми підставляємо певний набір Pn=1, при цьому зм(нн( p1..pq не змінюють своїх значень під час проходу по ГСА. Таким чином, якщо у вершину Аi перехід завжди здійснюється при незмінному значенні pq, то це значення pq в рядку Аi замінимо на “1", а його інверсію на “0". Наприклад, у вершину А3 перехід здійснюється при незмінному значенні (p1 і (p2, отже в рядку А3 (p1 і (p2 замінимо на “1", а p1 і p2 на “0". У результаті отримаємо формули F3,4=(p3, F3,11=p3. Керуючись вищенаведеним методом, отримаємо мінімізовану МСА М0 (табл.1.8). По таблиці складемо формули переходу для об'єднаної ГСА Г0. Формулою переходу будемо називати сл(дуюче вираження: Ai(Fi,1А1+..+Fi,kАk, де Fi,j- відповідна формула переходу з мінімізованої МСА. У нашому випадку отримаємо сл(дуючу систему формул: A0((x1(p1(p2(p3A1+(p1(p2p3A1+p1(p2(p3A1+x1(x2(p1(p2(p3A2+x1x2(p1(p2(p3A3 + +(x1(p1p2p3A8+x1(p1p2p3A13+(p1p2(p3A14 A1((p1(p3A2+p1(p3A6+(p1p3A7 A2((p1(p2(p3A6+(p1p2p3A18+p1(p2p3A21 A3((p3A4+p3A11 A4(A5 A5(А6 Таблиця 1.7 Об`(днана МСА Мo A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A16 A17 A18 A19 A20 A21 A22 Ak _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ x1p1p x1p1p2_ A0 x1p1p2x1x2p1x1x2p1 2p3 p3 p1p2 p3+ p2p3 p2p3 p3 _ _ +p1p2p 3+ _ _ +p1p2p 3 _ _ _ _ _ A1 p1p2p3 p1p2pp1p2 3 p3 _ _ _ _ _ _ A2 p1p2p p1p2p 3 p1p2p 3 3 _ _ _ _ A3 _ p1p2p p1p2 3 p3 _ _ A4 _ p1p2 p3 _ _ _ A5 p1p2p 3 _ _ _ _ _ _ _ _ _ A6 p1p2p3 _ p1p2p p1p2p3 p1p2p3 p1p2 3 p3 _ _ _ _ _ _ A7 x3p1p2 x3p1p p1p2pp3 2p3 3 _ _ _ _ A8 x2p1p2 p1p2p3 p3 + _ _ +x2p1p 2p3 _ _ _ A9 p1p2p p1p2p 3 3 _ _ A10 p1p2p3 _ _ A11 p1p2p3 _ _ _ _ A12 p1p2p3 p1p2p3 _ _ _ A13 p1p2p3 p1p2p3 _ _ _ A14 _ _ x1p1p2x1p1p p3 2p3 _ _ _ A15 _ _ x3p1p x3p1p2 2p3 p3 _ _ A16 p1p2p 3 _ _ _ A17 p1p2p p1p2p3 3 _ A18 p1p2p3 _ _ A19 _ _ _ _ x1x2p1 x1x2p1px1p1p p2p3 2p3 2p3 _ _ A20 p1p2p3 _ _ A21 p1p2p3 _ _ A22 p1p2p3 Таблиця 1.8 Об`(днана м(н(м(зована МСА Мo A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A16 A17 A18 A19 A20 A21 A22 Ak _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ x1p1p x1p1p2_ A0 x1p1p2x1x2p1x1x2p1 2p3 p3 p1p2 p3+ p2p3 p2p3 p3 _ _ +p1p2p 3+ _ _ +p1p2p 3 _ _ _ _ A1 p1p3 p1p3 p1p3 _ _ _ _ _ _ A2 p1p2p p1p2p 3 p1p2p 3 3 _ A3 p3 p3 A4 1 A5 1 _ _ _ _ _ _ _ _ _ A6 p1p2p3 _ p1p2p p1p2p3 p1p2p3 p1p2 3 p3 _ _ A7 x3p3 p3 x3p3 _ _ A8 x2p2p3 p2p3+ _ +x2p2p 3 _ A9 p2 p2 A10 1 A11 1 _ _ A12 p2p3 p2p3 _ A13 p3 p3 _ A14 x1 x1 _ A15 x3 x3 A16 1 _ _ _ A17 p1p2p p1p2p3 3 A18 1 _ _ A19 x1x2 x1x2 x1 A20 1 A21 1 A22 1 A6((p1p2p3A2+(p1(p2(p3A7+(p1(p2p3A12+p1(p2(p3A19+(p1p2(p3Ak A7(x3p3A6+(p3A8+(x3p3A9 A8(x2p2p3A17+(p2(p3Ak+(x2p2p3Ak A9(p2A8+(p2A10 A10(A3 A11(Ak A12((p2p3A22+p2(p3A13 A13(p3A9+(p3Ak A14((x1A15+x1A16 A15(x3A6+(x3Ak A16(A12 A17(p1(p2(p3A2+(p1p2p3A6 A18(Ak A19(x1(x2A2+x1x2A20+(x1A21 A20(A17 A21(Ak A22(Ak При побудові системи дужкових формул переходу необхідно кожну формулу привести до вигляду Аx1+В(x1, де А і В -деякі вирази, а x1 і (x1-логічн( умови переходу. Формули переходу для вершин А3, А4, А5, А9, А10, А11, А13, А14, А15, А16, А18, А20, А21, А22 вже є елементарними (розкладеними), а в інших є вирази виду Аn(xj(А) +(xjpi(В). Тут pi відповідає чекаючій вершині (мал.1.6). Подібних вершин в об'єднан(й ГСА бути не повинно. Для їх усунення скористаємося сл(дуючим правилом: додавання виразу [PqАn] не змінить формулу, якщо набір Pq не використовується для кодування ГСА або вершина Аn в(дсутня в ГСА з кодом Pq. Таким чином, додаючи допоміжні набори, ми отримаємо можливість за допомогою елементарних перетворень звести формули до необхідного вигляду. Наприклад, формула A8(x2p2p3A17+(p2(p3Ak+(x2p2p3A спрощується таким чином A8=p3(x2p2A17+(x2p2Ak)+(p3(p2Ak=p3p2(x2A17+(x2Ak)+(p3(p2Ak= 1 Xj 0 Pi 0 1 Мал.1.6 Приклад чекаючо( вершини Pi =[(p3p2(x2A17+(x2Ak)]+p3p2(x2A17+(x2Ak)+(p3(p2Ak+[p3(p2Ak]=(p2Ak+p2(x2A17+( x2Ak). Тут вершина А8 не зустр(ча(ться у ГСА ,в кодах яких присутн( комб(нац(( (p3p2 ( p3(p2. Нижче наведено розклад ус(х неелементарних формул переходу. A0=p1((p2(p3A1)+(p1((x1(p2(p3A1+(p2p3A1+x1(x2(p2(p3A2+x1x2(p2(p3A3+ +(x1p2p3A8+x1p2p3A13+p2(p3A14)=p1((p2(p3A1)+[p1(p2(p3A1]+ +(p1(p2((x1p3A8+x1p3A13+(p3A14)+(p2((x1(p3A1+p3A1+x1(x2(p3A2+ +x1x2(p3A3))=p1((p2A1)+[p1p2A1]+(p1(p2(p3((x1A8+x1A13)+(p3A14)+ +(p2((p3((x1A1+x1x2A3+x1(x2A2)+p3A1))= p1A1+(p1(p2(p3( (x1A8+ +x1A13)+(p3A14)+(p2((p3((x1A1+x1(x2A3+(x2A2))+p3A1)) A1=(p1(p3A7+(p3A2)+p1(p3A6+[p1p3A6]= (p1(p3A7+(p3A2)+p1A6 A2=p1((p2p3A21)+(p1((p2(p3A6+p2p3A18)= p1((p2p3A21)+[p1(p2p3A21]+ +(p1((p2(p3A6+[p2(p3A6]+p2p3A18+[p3(p2A18])=p1((p2A21)+(p1((p3A6+ +p3A18)=p1((p2A21)+[p1p2A21]+(p1((p3A6+p3A18)=p1A21+(p1((p3A6+ +p3A18) A6=p1((p2(p3A19)+[p1(p2p3A19]+(p1(p2p3A2+(p2(p3A7+(p2p3A12+p2(p3Ak)= =p1(p2A19+[p1p2A19]+(p1(p2(p3A2+(p3Ak)+(p2((p3A7+p3A12))=p1A19+ +(p1(p2(p3A2+(p3Ak)+(p2((p3A7+p3A12)) A7=p3(x3A6+(x3A9)+(p3A8 A8=p3(x2p2A17+(x2p2Ak)+(p3(p2Ak=p3p2(x2A17+(x2Ak)+(p3(p2Ak= =[(p3p2(x2A17+(x2Ak)]+p3p2(x2A17+(x2Ak)+(p3(p2Ak+[p3(p2Ak]=(p2Ak+ +p2(x2A17+(x2Ak) A12=(p2p3A22+p2(p3A13+[p2p3A22]+[(p2(p3A13]=p3A22+(p3A13 A17=p1(p2(p3A2+[p1(p2p3A2]+(p1p2p3A6+[(p1(p2p3A6]=p1(p2A2+[p1p2A2]+ +(p1p3A6+[(p1(p3A6]=p1A2+(p1A6 A19=x1((x2A2+x2A20)+(x1A21 Об'єднану ГСА Г0 (мал.1.7) побудуємо відповідно до формул переходу, замінюючи кожну мітку Аi відповідною операторною вершиною Yt, а кожний вираз Xi і Pj відповідними умовними вершинами. -- Y1 Y10 Y8 Y9 Y11 Y5 Y8 Y9 Y1 Y8 Y5 Y2 Y13 Y17 Y8 Y3 Y14 Y15 Y7 Y16 Y17 Y18 Y5 Y18 Y2 Y9 Y20 Y5 Y10 Y9 Y1 Y5 Y12 Y1 Y20 Y10 Y12 A B |