Знаходиться мінімальна ДНФ системи булевих функцій.

3. Кон’юнкції одержаної ДНФ реалізуються в першій матриці ПЛМ, а самі функції – в другій матриці – диз’юнкцією відповідних кон’юнкцій.

Через велику трудомісткість відповідних алгоритмів знаходження мінімального числа вхідних змінних і мінімальної ДНФ системи булевих функцій практично можливе лише для функцій від невеликого числа змінних. Тому для розв’язку таких задач великої розмірності застосовуються евристичні алгоритми. Більше того, знаходження мінімального числа змінних і мінімальної ДНФ в загальному випадку може й не дати мінімальної площі ПЛМ. Дійсно, для системи функцій (табл. 3. ) мінімальне число змінних дорівнює трьом. А мінімальна ДНФ складається із 6 простих імплікант. Відповідно, ПЛМ, що реалізує функції і , показана на рис. 3. Вона

Рис. 3. . Схема ПЛМ, що реалізує систему функцій і .

містить 5 стовпців і 6 рядків. Сумарна площа ПЛМ дорівнює 30. Якщо в табл. 3. закреслити стовпці і , вийде система функцій, що представлена в табл. 3. .

Число вхідних змінних в одержаній системі булевих функцій не мінімальне. Однак мінімальна ДНФ системи має вигляд:

; ,

тобто містить чотири різні прості імпліканти. Реалізація одержаної системи

на ПЛМ представлена на рис. 3. . Сумарна

Таблиця 3. площа ПЛМ дорівнює .

№
	1 0 1 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0	0 1 1 0 0 0 1 1 1 1 0 0 1 0 0 1

Додаткову можливість скорочення площі

ПЛМ дає використання дужкових форм.

Розглянемо, наприклад, функції, ДДНФ

яких мають вигляд:

Рис. 3. . Схема реалізації системи функцій на ПЛМ.

При безпосередній реалізації їх на ПЛМ необхідно використовувати ПЛМ площею . Застосовуючи спосіб факторизації (дужкової мінімізації), функцію можна привести до вигляду

,

де . Тоді .

Одержані ДНФ реалізуються ПЛМ, представленою на рис. 3. , з сумарною площею .

Розглянемо деякі підходи до розв’язку другої задачі – задачі синтезу комбінаційних схем на ПЛМ, що випускаються серійно.

Позначимо - число входів; - число виходів; - число рядків ПЛМ. Хай задана для реалізації система булевих функцій характеризується наступними параметрами: , де - число аргументів перемикальних функцій; , де - число булевих функцій в системі; , де - число різноманітних простих імплікант системи булевих функцій. Простіше взяти для реалізації ПЛМ, на першій з них реалізувати перші функцій системи, на другій – наступні функцій і т. д., до того часу, доки не будуть реалізовані всі перемикальні функції. Очевидно, якщо функції вихідної системи попарно різні, то число ПЛМ буде мінімальне.

Приклад. Реалізувати систему булевих функцій: ;

; ; на () =

= (3. 2. 4) – ПЛМ.

В нашому випадку ; = 4; = 5; = 3; = 2; = 4. Реалізація функції може бути здійснена у відповідності з блок-схемою (рис. 3. ,а). Принципова електрична схема показана на рис. 3. , б.

Рис. 3. . Блок-схема (а) та електрична схема (б) реалізації системи

перемикальних функцій на ПЛМ.

Допустимо задана для реалізації на (- ПЛМ система перемикальних функцій характеризується такими параметрами: ; ; . Найпростіший спосіб побудови комбінаційної схеми полягає у наступному. Множину всіх простих імплікант системи ДНФ перемикальних функцій поділяється на підмножини, що не перетинаються, по імплікант в кожній. Число таких підмножин може бути не більшим . Імпліканти, що входять в одну підмножину, реалізуються на одній ПЛМ.

Приклад. Реалізувати на () = 3, 2, 3)-ПЛМ систему перемикальних

функцій: ;

.

Очевидно, ; ; . Одна із можливих реалізацій функцій показана на рис. 3. , де ;

; ; , а ;

.

Рис. 3. . Схема реалізації системи перемикальних функцій на ПЛМ.

Розглянемо випадок, коли , . . Реалізація таких систем перемикальних функцій схемами з мінімальним числом ПЛМ основана на методах декомпозиції перемикальних функцій. Мінімальній за числом ПЛМ схемі відповідає декомпозиція вихідної системи функцій на мінімальне число підсистем, кожна із яких містить не більше ніж функцій і не більше ніж кон’юнкцій. Якщо не перейматися про мінімальне число ПЛМ, то можна будувати схему із ПЛМ так. Виберемо із вихідної системи підсистему із функцій. Якщо число різних імплікант, що входять у вибрані функції, , то підсистема реалізується на одній ПЛМ. Якщо ж , то підсистема реалізується схемою із - ПЛМ. Із решти функцій виберемо наступні функції і поступимо аналогічним чином. Загальне число ПЛМ в одержаній за описаним способом схемі може досягати величини .

Найскладнішими для реалізації на ПЛМ являються системи функцій, для яких . В загальному випадку реалізація таких систем з мінімізацією числа ПЛМ здійснюється складними комбінаторними методами.

Аналіз комбінаційних схем

Задача аналізу комбінаційних схем є зворотною відносно задачі синтезу комбінаційних схем. Вихідними даними у цьому випадку є комбінаційна схема, Необхідно описати схему аналітичними формами функцій, що реалізує схема, у заданому функціональному базисі.

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

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

Необхідну аналітичну форму можна одержати після застосування операцій перетворення логічної інформації в заданій алгебрі.

; .

Виконуємо перетворення, користуючись законами і аксіомами булевої алгебри:

.

У результаті одержали МДНФ перемикальної функції:

.

Розділ 4. ПРОЕКТУВАННЯ ЦИФРОВИХ АВТОМАТІВ

З ПАМ’ЯТТЮ

4. 1. Канонічний метод структурного синтезу автоматів

з пам’яттю

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

В загальному випадку задача структурного синтезу автоматів з пам’яттю зводиться до пошуку способів побудови структурних схем складних автоматів на основі композиції деяких елементарних автоматів, тобто пошуку певних способів їх з’єднання між собою. Слід зауважити, що не при всякому виборі системи елементарних автоматів можна побудувати (шляхом їх композиції) будь-який структурний автомат. В разі, коли це можливо, говорять, що задана система елементарних автоматів структурно повна. Однак і на основі структурно повних систем елементарних автоматів ефективно розв’язати задачу структурного синтезу довільного автомата з пам’яттю поки що вдається тільки для структурно повних систем елементарних автоматів деякого спеціального типу.

Розглянемо один із таких методів синтезу, який дозволяє звести задачу структурного синтезу довільного автомата з пам’яттю до задачі синтезу комбінаційних схем. Цей метод називається канонічним методом структурного синтезу автомата з пам’яттю.

Канонічний метод структурного синтезу оперує з елементарними автоматами, що поділяються на два великих класи.

Перший клас складають елементарні автомати з пам’яттю, які називаються елементами пам’яті.

Другий клас складають елементарні комбінаційні автомати – логічні елементи.

Зведення задачі структурного синтезу довільного автомата з пам’яттю до задачі синтезу комбінаційних схем накладає обмеження на тип елементів пам’яті. Результатом роботи методу являються рівняння булевих функцій автомата в канонічній формі подання. Вихідні дані для початку роботи методу – абстрактний автомат з пам’яттю, заданий або графічним способом у вигляді графа, або матричним способом у вигляді таблиць переходів і виходів.

Канонічний метод структурного синтезу умовно можна розділити на наступні етапи:

- кодування;

- вибір елементів пам’яті автомата;

- вибір структурно-повної системи елементів;

- побудова рівнянь булевих функцій виходів і збудження автомата;

- побудова функціональної схеми автомата.

Розглянемо кожний із перелічених етапів детально.

Кодування

Довільний цифровий автомат з пам’яттю на абстрактному рівні подання може бути описаний у вигляді . При переході на структурний рівень подання кожна буква вхідного алфавіту автомата представляється як двійковий вектор або двійковий набір, число компонентів якого дорівнює числу фізично реалізованих вхідних каналів структурного автомата. Одним словом, кожна буква кодується двійковим вектором. Очевидно, мінімальне число фізично реалізованих вхідних каналів в автоматі може бути вирахуване за формулою

,

де - потужність алфавіту входів . Наприклад, якщо , то . Значить кожну букву можна закодувати двійковим вектором, що складається не менше, ніж із двох компонент, наприклад . Кожна буква вихідного алфавіту автомата також подається як двійковий вектор, число компонент котрого дорівнює числу фізично реалізованих вихідних каналів автомата. Аналогічно

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

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

Приклад. Абстрактний автомат Мілі заданий суміщеною таблицею переходів і виходів (табл. 4. 5). Кодування букв алфавітів зображено відповідними таблицями кодування (табл. 4. 6; 4. 7; 4.8). При цьому, оскільки , то ; ; .

Таблиця 4. 5 Таблиця 4. 5 Таблиця 4.7

Стани автомата	Вхідні сигнали		Вхідні сигнали	Код вхідних сигналів		Стани	Код станів

Таблиця 4. 8 Таблиця 4. 9

Вихідні сигнали	Код вихідних сигналів		Стани автомата	Вхідні сигнали
			01/00 01/01 10/00	00/10 00/11 01/01

Зауважимо, що в загальному випадку кожній букві, що кодується, може бути приписаний довільний двійковий вектор, але обов’язково дві різні букви (одного й того ж алфавіту) мають кодуватися різними двійковими векторами.

Якщо замінити у вихідній таблиці переходів і виходів букви на двійкові вектори, то одержимо так звану структурну таблицю переходів і виходів автомата (табл. 4. 9). На одержанні структурної таблиці переходів і виходів, етап кодування закінчується.

Вибір елементів пам’яті автомата.

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

При канонічному методі структурного синтезу автоматів як елемент пам’яті використовуються елементарні автомати Мура з двома станами, які мають повну систему переходів і виходів.

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

Повнота системи виходів означає, що різним станам автомата відповідають різні вихідні сигнали. Зазвичай нульовому стану елементарного автомата відповідає нульовий вихідний сигнал, одиничному – одиничний.

Очевидно, що число елементів пам’яті структурного автомата дорівнює числу компонент вектора його станів.

Як елементи пам’яті структурного автомата зазвичай використовуються - тригери; - тригери; - тригери; -тригери, які відповідають вимогам стосовно повноти переходів і виходів. Таблиці їх переходів подані табл. 4. 1 – табл. 4. 4 відповідно.

Таблиця 4. 1 Таблиця 4. 2 Таблиця 4. 3

Стани -тригера	Вхідний сигнал		Стани -тригера	Вхідний сигнал		Стани -тригера	Вхідні сигнали
	1

Таблиця 4. 4

Стани -тригера	Вхідні сигнали

Умовні графічні позначення синхронних тригерів і системи підграфів переходів, що пояснюють спосіб зміни стану тригерів, зображені на рис. 4. 1. Тригери мають тільки два стани: нульовий стан (і ) та одиничний ( і ). Входи , , , , , називаються інформаційними. Таблиці переходів тригерів складаються тільки для інформаційних входів. Всі інші входи являються допоміжними. Перехід тригерів з одного стану в інший визначається інформаційними сигналами, а момент переходу – перепадом синхросигналу (в даному випадку перепад з 0 в 1). Асинхронні входи тригерів і дозволяють встановлювати початковий стан тригерів. Для - тригера

Рис. 4. 1. Синхронні тригери: а – умовні графічні позначення;

б – система під графів переходів

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

Вибір функціонально-повної системи елементів.

Функціонування структурного автомата в часі припускає керування переключанням кожного елементарного автомата його пам’яті у відповідності із структурною таблицею переходів синтезованого автомата. Останнє здійснюється за допомогою спеціальної комбінаційної схеми, що підключається до інформаційних входів елементарного автомата пам’яті і реалізує перемикальні функції, які керують його переключенням. Такі перемикальні функції називаються функціями збудження елемента пам’яті. Загалом різних функцій збудження стільки, скільки різних інформаційних входів має елементарний автомат пам’яті в структурному автоматі, що синтезується.

Функція збудження будь-якого елемента пам’яті є довільною перемикальною функцією і для її реалізації комбінаційною схемою необхідно використати яку-небудь функціонально-повну систему логічних елементів.

Теоретичним фундаментом канонічного метода структурного синтезу автоматів з пам’яттю являється теорема про структурну повноту.

Теорема про структурну повноту. Всяка система, яка складається із якої-небудь функціонально-повної системи логічних елементів та елементарних автоматів Мура з нетривіальною пам’яттю, котрі мають повну систему переходів і повну систему виходів, є структурно-повною (тобто дозволяє синтезувати довільний цифровий автомат з пам’яттю).

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

Побудова рівнянь перемикальних функцій

збудження і виходів автомата

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

Вихідними даними для побудови таблиці істинності функцій збудження тригерів являється структурна таблиця переходів автомата і таблиця переходів елемента пам’яті.

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

Розглянемо приклад синтезу автомата Мілі. Для організації пам’яті використовуємо, наприклад, - тригери, а для побудови комбінаційних схем – елементи булевого базису.

На основі структурної таблиці переходів і виходів автомата (табл. 4. 9) і таблиці переходів - тригера (табл. 4.3) складаємо таблицю істинності перемикальних функцій збудження тригерів і перемикальних функцій виходів автомата (табл. 4. 10).

Таблиця 4. 10

Код ПС

Код СП

Код вх. сигналів

Вихідні сигнали

Функції збудження тригерів

x

x

x

x

x

x

x

x

ПС – початковий стан, СП – стан переходу; знаком „ x “ в таблиці істинності позначені довільні значення аргументів.

На підставі таблиці істинності автомата визначаємо МДНФ функцій збудження тригерів і функцій вихідних сигналів. Аргументами функцій є значення (тобто структурний вхідний сигнал ) та у початковому стані:

; ; ; ;

; ; ; .

Функціональна схема автомата зображена на рис. 4. 4, де УПС −

Рис. 4. 4. Функціональна схема автомата

установлення початкового стану, − тактуючі сигнали.

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

4. 2. Синтез мікропрограмних автоматів.

При описі функціонування різних засобів обчислювальної техніки досить часто використовується їх подання у вигляді сукупності керуючого і операційного автоматів (рис. 4. 10), який реалізує певну систему операцій. Кожній операції відповідає послідовність операторів (мікрооперацій). А кожному оператору відповідає сукупність структурних сигналів автомата із множини .

Рис. 4. 5. Загальна структура засобів обчислювальної техніки

Керуючий автомат (КА) може розглядатися як пристрій, який реалізує алгоритм функціонування, що визначає порядок виконання окремих операції чи процедур з керування деяким об’єктом – операційним автоматом (ОА).

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

Елементарний неподільний акт обробки інформації в операційному автоматі, що відбувається протягом одного моменту автономного часу (одного такта роботи автомата), називається мікрооперацією. Наприклад, „зсув інформації”, „+1”, „інвертування змінної”, тощо.

Якщо в операційному автоматі одночасно реалізується кілька

мікрооперацій, то така множина мікрооперацій називається мікрокомандою. Бувають випадки, коли множина мікрооперацій , що утворює мікрокоманду, порожня. Реалізація такої мікрокоманди в ОА рівнозначна відсутності виконання будь-яких елементарних операцій. В синхронних дискретних пристроях порожня мікрокоманда інтерпретується як пропуск такту, коли від керуючого автомата ніякі сигнали не надходять на операційний автомат.

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

Сукупність мікрокоманд і функцій переходу утворює мікропрограму. Таким чином, для описання мікропрограми необхідно задати множину мікрокоманд і функцій переходу, що визначають порядок їх виконання.

Послідовність сигналів, що виробляються керуючим автоматом, залежить від стану самого КА і зовнішнього сигналу , який може надходити ззовні, наприклад, від іншого КА або від людини.

Як систему КА – ОА можна розглядати звичайну ЕОМ, в котрій КА являється процесор, а операційним пристроєм – запам’ятовуючий пристрій (ЗП). Якщо ЕОМ включена в цикл керування яким-небудь об’єктом, то КА такої системи являється уже вся ЕОМ.

При необхідності детальнішого розгляду функціонування самого процесора ЕОМ у вигляді системи „КА – ОА” як КА розглядається центральний блок (пристрій) керування (ЦБК), а як ОА – арифметико- логічний пристрій (АЛП).

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

Абстрактний синтез автоматів з пам’яттю

Результатом абстрактного синтезу автомата є його формальний опис сукупністю п’яти об’єктів , де , − вхідний алфавіт автомата; , − вихідний алфавіт автомата; , − алфавіт станів автомата; − функція переходів автомата , яка задає відображення множин , тобто яка ставить у відповідність будь-якій парі елементів декартового добутку множин елемент ; − функція виходів автомата, яка задає відображення , або . Отже, функція переходів визначає спосіб переходу автомата із одного стану в інший, а функція виходів – формування вихідних сигналів.

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

Абстрактний синтез складається з таких етапів:

- формування вхідного та вихідного алфавітів;

- складання алгоритму функціонування автомата;

- формування алфавіту внутрішніх станів автомата;

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

Вхідний алфавіт формується на основі вивчення зовнішніх для автомата сигналів, які можуть розглядати як логічні умови, що змінюють режим функціонування автомата. Різні комбінації вхідних сигналів розглядаються як букви вхідного алфавіту.

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

Для отримання алгоритму функціонування автомата необхідно чітко представляти спосіб перетворення інформації.

Для опису алгоритмів функціонування цифрового автомата зручно використовувати графічні схеми алгоритмів (ГСА).

Граф схемою алгоритму називається орієнтований зв’язаний граф, який має одну початкову вершину („Початок“), одну кінцеву вершину („Кінець“) і довільну кінцеву множину умовних і операторних вершин.

ГСА складається з вершин чотирьох типів (рис. 4. 1). Алгоритм починається з вершини „Початок“ і закінчується вершиною „Кінець“. Букви вихідного алфавіту (вихідні сигнали, оператори) записують в операторні вершини, а букви вхідного алфавіту (вхідні сигнали, логічні умови) розміщують у логічні (умовні) вершини.

Кожна вершина ГСА, крім вершини „Початок“, має по одному входу. Вершина „Початок“ і кожна операторна вершина, крім вершини „Кінець“ мають по одному виходу. Кожна умовна вершина має два виходи, позначені символами „Так“ і „Ні“ (замість цих символів можуть бути використані цифри 1 і 0 відповідно).

ГСА має задовольняти наступним умовам: 1. Входи і виходи

Рис. 4. 6. Умовні позначення вершин з’єднуються один з одним за

вершин ГСА допомогою дуг, направлених завжди

від виходу до входу;

2. Кожний вихід з’єднується тільки з одним входом;

3. Будь-який вхід з’єднується принаймні з одним виходом;

4. Будь-яка вершина ГСА лежить принаймні на одному шляху із вершини „Початок“ до вершини „Кінець“;

5. Один із виходів умовної вершини може з’єднуватися із її входом, що не допустимо для операторної вершини;

В кожній умовній вершині записується логічна умова (вхідний сигнал) із множини логічних умов. Дозволяється в різних умовних вершинах записувати однакові логічні умови;

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

Після створення ГСА процес побудови графа автомата і визначення алфавіту внутрішніх станів можна формалізувати. У зв’язку з цим ГСА, як і граф, можна вважати формальним описом абстрактного автомата.

Для побудови графа автомата виконується розмітка станів автомата на ГСА. Способи розмітки автоматів Мура і Мілі відрізняються.

Розмітка станів автомата Мілі здійснюється таким чином:

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

− входи всіх вершин, наступних за операторними, позначаються символами .

Розмітка станів автомата Мура здійснюється за такими правилами:

− символом позначаються початкова і кінцева вершини;

− всі операторні вершини позначаються різними символами .

У результаті розмітки ГСА визначається алфавіт внутрішніх станів.

Побудова графа автомата виконується на основі розміченої ГСА. Число вершин графа дорівнює числу станів автомата. Кожному переходу автомата з одного стану в інший відповідає дуга графа. Дузі приписується умова, за якої здійснюється перехід автомата з одного стану в інший. Для автомата Мілі вихідні сигнали приписують дугам, а для автомата Мура – розміщують у вершинах графа. Приклади графів абстрактних автоматів наведені на рис. 2. 3.

Структурний синтез автоматів з пам’яттю

Результати абстрактного синтезу автомата можуть розглядатися як вихідні дані для структурного синтезу. Під час проектування реальних систем на етапах структурного синтезу може виникнути необхідність корегування результатів абстрактного синтезу (наприклад, ГСА та графа автомата). Це може зумовлюватися необхідністю усунення ризиків збою, врахуванням тривалості структурних сигналів, елементної бази тощо. Таке корегування може привести до введення нових вершин і дуг в граф автомата. Таким чином, множина станів абстрактного автомата може відрізнятися від множини станів структурного автомата .

Структурний синтез синхронного автомата включає такі етапи:

- складання списку структурних вихідних сигналів, що відповідають кожній букві вихідного алфавіту абстрактного автомата;

- визначення тривалості кожного вихідного структурного сигналу (в числі тактів) і періоду тактуючих сигналів автомата;

- одержання закодованої ГСА структурного автомата, тобто корегування ГСА абстрактного автомата, якщо сигнали мають різну тривалість;

- розмітка ГСА структурного автомата;

- складання графа структурного автомата;

- кодування станів структурного автомата;

- вибір елементів пам’яті і структурно повної системи логічних елементів (якщо вони не задані);

- складання структурної таблиці автомата;

- одержання МДНФ функцій збудження тригерів і керуючих сигналів (виходів автомата);

- вираження функцій збудження тригерів і керуючих сигналів в операторній формі;

- побудова схеми керуючого автомата.

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

Нехай на етапі абстрактного синтезу одержана ГСА в абстрактних термінах (рис. 4. 7).

Відповідність абстрактних та структурних сигналів визначається особливостями керування операційним пристроєм. Нехай за рахунок аналізу пристрою одержана відповідність зазначених сигналів (табл. 4. 11).

На практиці необхідна тривалість керуючих сигналів визначається з урахуванням затримок в елементах операційного пристрою. Виходячи з цього обирається період тактуючих сигналів. При цьому величина має бути не менше часу переключення автомата з одного стану в інший.

Як видно з табл. 4. 11, керуючі сигнали і повинні мати тривалість , а інші − . Подвійна тривалість сигналів може бути забезпечена, наприклад, введенням у ГСА додаткових операторних вершин з керуючими сигналами, тривалість яких перевищує .

Для одержання ГСА автомата в структурних термінах (структурної ГСА) складаємо таблицю позначень логічних умов (табл. 5) і замінюємо абстрактні терміни в ГСА (рис. 7) на структурні. Оскільки управляючі сигнали та мають тривалість , то на структурній ГСА Рис. 8) вводимо додаткову операторну вершину 4, що відповідає цим управляючим сигналам.

На рис. 8 ГСА відзначена чотирма різними станами (). Таку саму кількість вершин має граф автомата Мілі, зображений на рис.9.

Кожному переходу автомата з одного стану в інший відповідає дуга графа. Дузі приписується логічна умова, за якої здійснюється перехід автомата з одного стану в інший, а також набір управляючих сигналів, що відповідають даному переходові. Якщо перехід безумовний, то замість умови проставляють „−“.

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

Для прикладу, що розглядається, вибираємо коди станів відповідно до табл. 6.

Для організації пам’яті використовуємо -тригери, а для побудови комбінаційних схем – елементи булевого базису.

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

Структурна таблиця автомата складається за його графом. Кожен рядок (табл. 7) відповідає визначеному переходові автомата з одного стану в інший. У рядку записують вихідний стан, стан переходу, коди цих станів, значення логічних умов, що забезпечують перехід, необхідні значення управляючих сигналів і функцій збудження тригерів. Значення функції збудження тригерів визначають згідно з таблицею переходів тригера відповідного типу. В кожному рядку для -го тригера розглядаються переходи . Довільні значення управляючих сигналів (0 або 1) позначаються в структурній таблиці символом „−“. Довільні значення управляючих сигналів визначаються особливостями операційного пристрою. В даному випадку як приклад такі значення прийняті для сигналів .

На підставі структурної таблиці автомата визначаємо МДНФ функцій збудження тригерів і функцій управляючих сигналів. Аргументами функцій та є значення та у початковому стані.

Для отримання МДНФ функцій використовуємо діаграми Вейча (рис.10).

Після мінімізації одержимо функції:

;

;

;

;

;

;

.

Функціональна схема автомата зображена на рис. 11, де УПС − установлення початкового стану (активний рівень сигналу низький), − тактуючі сигнали.

Розглянемо приклад синтезу автомата Мура на - тригерах та елементах булевого базису.

Будемо вважати, що одержано таку саму ГСА структурного автомата, як у попередньому прикладі (рис. 7). Після розмітки станів за правилами автомата Мура структурна ГСА приймає вигляд, наведений на рис. 12, а граф автомата мура – як на рис. 13.

Кодування станів автомата Мура виконаємо аналогічно до розглянутого у прикладі автомата Мілі (табл. 7).

На основі графа складаємо структурну таблицю автомата Мура (табл. 8).

Вихідні сигнали в автоматі Мура залежать тільки від початкового стану і . Функції збудження тригерів, як і для автомата Мілі, залежать від початкового стану і вхідних сигналів.

На підставі структурної таблиці автомата визначаємо МДНФ функцій збудження тригерів і функцій управляючих сигналів, для чого використовуємо діаграми Вейча (рис. 14).

Після мінімізації одержимо функції:

;

;

;

;

;

;

.

Функціональна схема автомата показана на рис. 4.

4.3. Забезпечення стабільної роботи автоматів.

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

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

Розглянемо питання забезпечення стабільності роботи автомата детальніше.

Після надходження чергового вхідного сигналу і формування сигналу збудження на входах елементів пам’яті автомат переходить в новий стан. При цьому відбувається формування нових сигналі збудження по ланцюгах зворотних зв’язків (з виходів елементів пам’яті через логічні елементи на входи елементів пам’яті), і автомат переходить в новий стан і т. д. Таким чином, автомат загалом не може зупинитися в якому-небудь певному стані і починає працювати в режимі генератора станів. Для усунення такого ефекту використовують тактування – послідовність спеціальних (зазвичай прямокутних) сигналів, що подаються на входи елементів пам’яті і дозволяють надходження чергових сигналів збудження на входи елементів пам’яті тільки з приходом чергового синхросигналу. При відсутності синхросигналу сигнал збудження не надходить на вхід елемента пам’яті і він не переключається, тобто залишається в якому-небудь стані. Тактуючі сигнали підключають до спеціальних входів елемента пам’яті, які позначаються на рисунках символом і називаються синхровходами.

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

- якщо черговий синхросигнал на вхід елементів пам’яті автомата надходить раніше, ніж закінчилися перехідні процеси в його комбінаційній схемі збудження і елементах пам’яті після надходження вхідного сигналу, то можливе неправильне формування сигналу збудження на вході одного або кількох елементів пам’яті автомата, тобто автомат може замість правильного переходу здійснити хибний перехід;

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

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

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

Перехідні процеси в логічних елементах.

Логічним схемам властиве явище затримки спрацьовування. Затримки логічних елементів складаються із затримок їх спрацьовування і затримок поширення сигналів ланцюгами зв’язку між ними. Значну складність врахування затримок становить співвідношення значень затримок самих логічних елементів і затримок в ланцюгах зв’язків. Якщо затримки логічних елементів розмірні, то затримки різних трактів схеми можна визначити тільки після розміщення логічних елементів на поверхні плати чи кристала ВІС, тобто коли стануть відомі фактичні довжини зв’язків. Якщо затримки деяких ланцюгів зв’язків не відповідають вимогам, то виникає ітераційний процес переставлення елементів, який може бути досить тривалим.

В цифрових схемах зазвичай використовуються логічні елементи з часом переключання 10 – 20 нс, що приблизно на порядок перевищує затримку поширення сигналів в будь-якому провіднику монтажної плати типового розміру. Паразитна ємність монтажу при використанні типових плат також не настільки велика, щоб суттєво змінити затримку елемента. В такому разі: затримку монтажу в платі і близького між платного монтажу раціонально не враховувати окремо, а включати її в склад затримки логічного елемента; такі технічні етапи проектування, як розміщення елементів і трасировка зв’язків, виконуються теж тільки один раз і не викликають необхідності корегування функціональної схеми.

Надалі будемо вважати, що затримки в ланцюгах зв’язку включені в затримки логічних елементів.

Ситуації, коли затримки в зв’язках перевищують затримки в елементах, виникають при використанні не дуже швидкодіючих елементів і при передачі сигналів між блоками, розміщеними на значній відстані. Але такі ситуації можна окремо вилучити і врахувати затримку в кабелі.

Затримки різних екземплярів елементів якого-небудь певного типу мають технологічний розкид, який зазвичай описують деяким статистичним законом. Крім того, затримки кожного конкретного елемента залежать від: температури; фронту вхідного імпульсу; на скільки (і які) елементів він навантажений; паразитної ємності монтажу; часу роботи з моменту випуску, тощо.

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

Ефективним засобом аналізу перехідних процесів в схемах є часові діаграми. При їх побудові стани невизначеності схеми, тобто такого стану, який розробнику невідомий, зображають одним із двох способів. Розглянемо їх на прикладі елемента І (див. рис. 4. 5).

Рис. 4. 5. Часові діаграми логічного елемента І.

Визначення.