Главная | Обратная связь | Поможем написать вашу работу!

Загальні відомості про цифрові автомати

Для позначення різноманітних предметів, понять і дій люди користуються словами. Слова складаються з букв, які утворюють алфавіт. У цифровій техніці використовують кодові слова на основі найпростішого алфавіту, що складається лише з двох символів – 0 і 1. Ці символи називають логічним нулем і логічною одиницею. Причина вибору такого простого алфавіту – зручність збереження і передавання інформації, закодованої за допомогою логічних нулів і одиниць. Дійсно, можна, наприклад, домовитися, що стан пристрою, коли на його виході є сигнал, відповідає логічній одиниці, а стан „немає сигналу” – логічному нулю. Очевидно, що при такому способі подання інформації цифровий сигнал являє собою кодове слово визначеної довжини (розрядності), передане як „ланцюжок букв” (послідовність символів), і має вигляд аперіодичної імпульсної послідовності, приведеної на рисунку 1.1.

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

Рис.1 Цифровий сигнал.

Алгебру логіки, що є математичним апаратом теорії цифрових (логічних) схем, нерідко називають булевою алгеброю на честь її засновника Дж. Буля. Іноді для ЛФ використовують назву „перемикальні функції”.

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

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

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

ЦА поділяють на дві великі групи –комбінаційні (ЦА без пам’яті) і послідовнісні (ЦА з пам’яттю).

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

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

Автомати з пам’яттю в канонічному поданні розділяють на дві частини: пам’ять та комбінаційне коло (логічний перетворювач). На входи комбінаційної частини подаються вхідні сигнали та сигнали стану ЦА. На її виході виробляються вихідні сигнали та сигнали переводу ЦА в наступний стан або сигнали керування пам’яттю (тому комбінаційну частину іноді розділяють за функціональним призначенням на два кола). Відповідна структурна схема ЦА з пам’яттю подана на рис. 1.2 а.

Рис. 1.2. Структурні схеми ЦА: автомат з пам’яттю (а), автомат Глушкова (б)

Тут X та Y – множини вхідних та вихідних сигналів ЦА відповідно, U – множина сигналів керування пам’яттю, Y – множина вихідних сигналів блока пам’яті або сигнали стану ЦА.

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

ЛФ, що встановлює залежність стану, у який переходить послідовнісний пристрій із поточного стану під впливом заданих сигналів управління, має назву функції переходів. Переходи автоматів з пам’яттю з одного стану до іншого починаються з деякого початкового стану, визначення якого є частиною визначення умов функціонування ЦА в цілому. Наступний стан ЦА залежить від вихідного стану та вхідних сигналів. У результаті, поточний стан і сигнали на виходах ЦА залежать від початкового стану та всіх попередніх вхідних сигналів, тобто послідовність вхідних сигналів визначає послідовність станів та вихідних сигналів автомата. Цим пояснюється назва „послідовнісні схеми”, яку використовують для позначення ЦА з пам’яттю.

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

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

З метою спрощення аналізу і синтезу логічний перетворювач ЦА з пам’яттю зручно подавати у вигляді двох частин: блока формування вихідних сигналів та блока керування пам’яттю (у реальних ЦА наявність чітко відокремлених двох блоків необов’язкова). Якщо вхідні сигнали подаються тільки на входи блока керування пам’яттю, то вихідні сигнали ЦА будуть функціями виключно попередніх станів ЦА. Такі автомати називають автоматами Мура. У автоматах Мілі вихідні сигнали залежать як від попередніх станів, так і від вектора вхідних змінних. Структурні схеми автоматів Мілі і Мура подані на рис. 1.3, а та 1.3, б відповідно.

Рис. 1.3. Структурні схеми ЦА: автомат Мілі (а), автомат Мура (б)

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

Складні ЦА автомати частіше всього містять у собі і комбінаційну, і послідовнісну частини.

Класифікувати ЦА можна ще за багатьма ознаками.

За способом введення і виведення кодових слів розрізняють ЦА послідовної, паралельної і змішаної дії.

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

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

У пристроях змішаної дії вхідні і вихідні кодові слова подаються у різних формах. Наприклад, вхідне слово – у послідовній формі, вихідне – у паралельній. Пристрої змішаної дії можна використовувати для перетворення кодових слів з однієї форми подання в іншу (із послідовної – у паралельну і навпаки).

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

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

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

Структурна схема синхронного ЦА подана на рис. 1.4.

Рис. 1.4. Структурна схема синхронного ЦА

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

1.2. Логічні основи цифрової обчислювальної техніки

Елементарні ЛФ та їх властивості.

У математиці для подання функції переважно використовують два способи: аналітичний і табличний. Ці ж два способи використовують і для запису ЛФ.

При використанні табличного способу будується таблиця істинності, у якій наведені усі можливі сполучення значень аргументів і відповідні значення ЛФ. Якщо число аргументів ЛФ дорівнює n, то число різноманітних сполучень (наборів) значень аргументів складає 2 ⁿ, а число різноманітних ЛФ n аргументів – . При n = 1 число всіх можливих ЛФ одного аргументу дорівнює 4. Вони можуть бути подані таблицею істинності 1.1.

Таблиця 1.1

Аргумент Х	Ф у н к ц і ї
F ₁ (x)	F ₂ (x)	F ₃ (x)	F ₄ (x)

Функції і не залежать від значень аргументу х, дорівнює значенню аргументу. Отже, практичний інтерес має лише . Це – функція „НІ” (логічне заперечення, інверсія). Вираз читається як „ y є не x ”.

Для двох аргументів (n = 2) кількість можливих ЛФ дорівнює 16, вони можуть бути подані таблицею істинності 1.2.

Таблиця 1.2

Аргу-менти

Ф у н к ц і ї

Х₁

Х₂

F₀

F₁

F₂

F₃

F₄

F₅

F₆

F₇

F₈

F₉

F₁₀

F₁₁

F₁₂

F₁₃

F₁₄

F₁₅

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

Шість функцій, що залишилися, розглянемо більш детально.

1. (додаткові позначення: ). Це операція „логічне ТА” (кон’юнкція, логічне множення). Як видно з таблиці істинності, у результаті виконання операції ТА утворюється функція, значення якої дорівнює 1 тільки тоді, коли значення всіх аргументів рівні 1, і дорівнює 0, коли значення хоча б одного з аргументів дорівнює 0.

2. (додаткове позначення ). Це операція „логічне АБО” (диз’юнкція, логічне додавання). У результаті виконання операції АБО утворюється функція, значення якої дорівнює 1, коли значення хоча б одного з аргументів дорівнює 1, і дорівнює 0 тільки в тому випадку, коли значення всіх аргументів дорівнюють 0.

3. . З таблиці видно, що . Тому дану операцію називають „логічним ТА-НІ”, або запереченням кон’юнкції. Нерідко використовується назва „штрих Шеффера”. У результаті виконання операції ТА-НІ утворюється функція, значення якої дорівнює 1, коли значення хоча б одного з її аргументів дорівнює 0, і дорівнює 0 тільки в тому випадку, коли значення всіх аргументів рівні 1.

4. . З таблиці видно, що . Тому дану операцію називають „логічним АБО-НІ” або запереченням диз’юнкції. Також використовуються назви „стрілка Пірса” і „функція Вебба”. У результаті виконання операції АБО-НІ утворюється функція, значення якої дорівнює 1 тільки тоді, коли значення всіх аргументів рівні 0, і дорівнює 0, коли значення хоча б одного аргументу дорівнює 1.

5. (додаткове позначення x₁ x₂). Це функція нерівності (виключальне АБО, сума за модулем 2). У результаті додавання за модулем 2 утворюється функція, значення якої дорівнює 1, коли значення аргументів не співпадають, і дорівнює 0 у протилежному випадку.

Покажемо, що ця функція також може бути виражена через операції ТА, АБО, НІ:

Точність цієї рівності доведемо за допомогою таблиці істинності 1.3.

Таблиця 1.3

Остання колонка цієї таблиці співпадає з колонкою F₆ із таблиці 2, тобто рівність правильна.

6. (Додаткове позначення x₁ x₂). Це операція рівності (еквівалентності). У результаті виконання операції рівності утвориться функція, значення якої дорівнює 1, коли значення аргументів співпадають, і дорівнює 0 у протилежному випадку.

Очевидно, що .

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

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

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

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

Наприклад, вираз припускає таку послідовність дій:

1. .

2. .

3. .

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

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

Таблиця 1.4

Закон	Логічне додавання	Логічне множення
1.	Переставний
2.	Сполучний
3.	Розподільний
4.	Інверсії

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

Переставний закон: від перестановки доданків і співмножників результат не змінюється.

Сполучний закон: при зміні порядку виконання однакових операцій результат не змінюється.

Розподільний закон коментарів не потребує.

Закон інверсії (теорема де Моргана) говорить про те, що операція АБОможе бути виражена через операції ТА, НІ і навпаки:операція ТА може бути виражена через операції АБО, НІ.Дійсно, вирази для закону інверсії, записані в рядку 4 таблиці 1.4, можуть бути подані у вигляді:

або .

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

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

Першою функціонально повною системою є набір елементарних ЛФ ТА, АБО, НІ. Його також називають універсальним або булевим базисом. При синтезі логічних пристроїв ця система дозволяє більш просто перейти від табличного подання функції до аналітичного, а потім – до функціональної схеми на відповідних цифрових електронних елементах. Проте із теореми де Моргана витікає, що ця система має надмірність і з неї можна виключити деякі функції без втрати функціональної повноти.

Основні функціонально повні системи ЛФ:

1. АБО, НІ – виключена функція ТА;

2. ТА, НІ – виключена функція АБО;

3. АБО-НІ;

4. ТА-НІ.

Існують і інші функціонально повні системи ЛФ. Але найбільш широко застосовують системи, що складаються всього з однієї функції (АБО-НІ, ТА-НІ).

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

Таблиця 1.5

№	Правило	а	б
1.	Інверсії
2.	Незмінності
3.	Універсальної і нульової множини
4.	Повторення
5.	Додатковості
6.	Склеювання
7.	Подвійного заперечення

У правильності перших п’яти правил неважко переконатися, аналізуючи таблиці істинності ЛФ ТА, АБО, НІ.

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

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

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

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

Розглянемо цей метод на прикладі.

Мінімізуємо ЛФ, яка має вигляд:

За розподільним законом:

У першому логічному доданку є логічний добуток (правило 5б). Отже, на підставі правила 3б перший логічний доданок дорівнює 0 і його можна опустити (правило 2а). У другому і третьому доданках є логічні добутки і (правило 4б). Остаточно маємо:

Застосовуючи до першого і третього доданків розподільний закон, маємо:

Згідно з правилами 5а і 2б:

У останньому виразі можна винести за дужки. Остаточно маємо:

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

⇐ Предыдущая 123 4 5 6 7 8 9 10 Следующая ⇒