Щербаков а. Н., Проскурін м. П., Грушко с. С. Прикладна теорія цифрових автоматів

• Название: Щербаков а. Н., Проскурін м. П., Грушко с. С. Прикладна теорія цифрових автоматів
• Анкор: Ukr1_PTTsA_kl_ch1_10-02-2010.doc
• Дата: 13.02.2018
• Размер: 2.54 Mb.
• Имя файла: Ukr1_PTTsA_kl_ch1_10-02-2010.doc
• Тип: Протокол; #15521
• страница: 2 из 26

1 ОСНОВНІ ВИЗНАЧЕННЯ І СКЛАД КОМП’ЮТЕРНИХ СИСТЕМ

1.1 Мета дисципліни

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

Курс умовно роздільний на дві частини:

- частина 1 - «Комп’ютерна арифметика»;

- частина 2 - «Логічні основи і синтез цифрових автоматів».

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

У другій частині курсу вивчаються логічні основи цифрових автоматів, математичний апарат булевої алгебри, методи мінімізації булевих рівнянь, описи цифрових автоматів (ЦА), методи синтезу і аналізу ЦА (в т.ч. канонічні) на логічних елементах різних базисів, графи і граф схеми автоматів (ГСА). Контроль правильності виконання арифметичних і логічних операцій пристроями. Студенти повинні отримати практичні навики проектування елементарних, логічних і принципових електричних схем типових комбінаційних цифрових автоматів і автоматів з пам’яттю.

1.2 Загальні визначення і математична модель цифрових автоматів

У загальному випадку, всі електронні пристрої, у тому числі і ЕОМ, ділять на аналогові, цифрові і змішані.

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

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

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

У словнику С.І. Ожегова наведено: інформація  відомості про навколишній світ і процеси, що протікають в ньому, сприймані людиною або спеціальними пристроями.

Комітет науково-технічної термінології Академії наук дає наступне визначення: інформація  це відомості, зберігання, що є об’єктом передачі і перетворення [1-21]. Можна зупинитися на такому визначенні: інформація  це відомості про яку-небудь подію або предмет, що поступає до одержувача ззовні в результаті його взаємодії з навколишнім середовищем [1-21].

Як усяка категорія інформація характеризується наступними властивостями [1-21]:

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

- інформація не матеріальна, але вона виявляється у формі матеріальних носіїв (дискретних знаків, символів, сигналів і ін.);

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

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

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

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

Розрізняють інформацію безперервну і дискретну.



Рисунок 1.1  Інформація функції f(t) представлена в безперервному (аналоговому) і дискретному вигляді

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

Вид інформації, що переробляється, впливає на структуру ОМ і принцип їх дії. Як наголошувалося раніше, ОМ ділять на три основні класи: аналогові, цифрові, гібридні.

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

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

Останніми роками при розробці деяких ОМ вчені суміщають пози-тивні сторони ЦОМ і АОМ. Такі машини отримали назву гібридних ОМ.

Ми розглядатимемо арифметичні і логічні основи ЕОМ з погляду теорії цифрових автоматів. Відомий математик Джон фон Нейман у 1945р. у своїй доповіді описав, як повинен бути влаштований комп’ютер. У спрощеному вигляді, він повинен мати наступну структуру (рис 1.2).



Рисунок 1.2  Структура ЕОМ

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

Нас цікавлять теоретичні основи методів виконання арифметичних і логічних операцій АЛП. Загалом, будь-який пристрій ЕОМ можна представити як цифровий мікропрограмний автомат.

Під цифровим автоматом (ЦА) розуміють пристрій, що оперує з цифровою дискретною інформацією і характеризується кінцевою множиною внутрішніх станів Z={z₀,z₁,z₂,…,z_n}, в які він переходить під впливом множин сигналів: вхідних Х={х₁,х₂,...,x_k} і вихідних Y={y₁,y₂,...,y_m}, при цьому є кінцева множина правил переходу з одного стану в інший: W={w₁,w₂,...,w_L} - функція переходів ЦАіз стануZ_i-1 у Z_iпо правилам формування Z_i, станів ЦА; а також функція λ={λ₁,λ₂...,λ_j} формування Y- виходів ЦА, що в загальному випадку може бутипов’язана з його станом Z_i і вхідними сигналами Y=λ[Z_i, X_i]). Всі множини є кінцеві, звідси кінцевий ЦА.

Математичною моделлю ЦА є деякий абстрактний автомат, заданий таким чином: у початковий момент t₀ автомат знаходиться в стані Z₀. Під впливом вхідного коду X з множини вхідних слів, автомат переходить зі стану Z₀ в Z₁, при цьому може виникнути вихідне слово Y=λ[Z_i,X_i], а перехід Z_i =W[Z₀,X_i] здійснюється функцією переходів W, дії вхідного коду X і попереднього стану Z_{0 (або n)} і так далі (алгоритм перетворення).


Рисунок 1.3  Модель абстрактного автомата

У загальному випадку математична модель абстрактного автомата записується як кортеж (сукупність): A={X, Z₀, Z, W, λ, Y}.

Алгоритм  кінцева послідовність точно сформульованих правил рішення якоїсь задачі (узбецький математик Аль-Хорезмі в IX столітті сформулював правила арифметичних дій). Можуть бути словесними, математичними, заданий програмою, ін.. Бувають детерміновані алгоритми, випадкові алгоритми, чисельні алгоритми, логічні алгоритми.

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

АЛП характеризується:

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

- набором арифметичних дій і логічних команд, які він виконує;

- видом арифметичного базису;

- тактовою частотою (часова сітка) виконання операцій, її швидкодія.

Наприклад, частота 100 МГц позначає, що виконується 100 мл. тактів в секунду (якщо операція виконується за два такти, то швидкодія буде 50 мл. операцій в секунду).

Одиницею інформації в комп’ютері є один біт, тобто двійковий розряд, який може приймати значення 0 або 1. Вісім послідовних або паралельних бітів складають байт. У одному байті кодується значення одного повідомлення з 256 можливих. Продуктивність АЛП процесора додатково характеризується наступними параметрами: внутрішньою і зовнішньою розрядністю даних, що обробляються (чим вище розрядність, тим вище інформаційна продуктивність одночасно обробляємої інформації); об’ємами пам’яті, адресацією центрального процесорного пристрою CPU (central processor unit); ступенем інтеграції транзисторів, ін..