Прикладна теорія цифрових автоматів

Міністерство освіти України

Вінницький державний технічний університет

кафедра обчислювальної техніки

Допущено до захисту:

1999р.

Керівник роботи:

Очкуров М. А.

(підпис)

Захищена_____________ 1999р.

з оцінкою_________________

КУРСОВА РОБОТА

з дисципліни:

«Прикладна теорія цифрових автоматів»

Технічне завдання № 60.

Виконав: Швець О. М.

група 2КІ-97

Залікова книжка № 97-108

Вінниця 1999.

Зміст

1.Вступ

2.Технічне завдання.

3.Розробка машинного алгоритму операції.

3.1.Основні способи виконання операції множення.

3.2.Множення чисел в прямому коді що представлені у формі з плаваючою комою, починаючи зі старших розрядів з групуванням розрядів множника.

3.3.Розробка алгоритму та операційного автомату.

3.4.Алгоритм

3.5. Приклад виконання для множення в прямих кодах з групуванням розрядів множника починаючи з старших розрядів

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

5.Синтез керуючого автомату.

6.Заключення.

7.Список літератури.

1. Вступ

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

Використання електронних ламп дозволило різко підвищити швидкість виконання машинних операцій: додавання - 0, 0002 с., множення - 0, 0028 с. Управління рахунком здійснювалось за допомогою програм, що набираються вручну на численних коммутацiйних дошках та перемикачах. Невідповідність між часом рішення задачі та часом її підготовки вручну було настільки більшим , що виграш від швидкості обчислення майже повністю покривався програшем у часі на підготовчих операціях.

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

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

Спеціально вирощені великі кристали кремнiю, пластини, що мають дуже високий ступінь хімічної чистоти, розрізаються на окремі, на поверхні яких або усередині спеціальним способом формуються ділянки, володіючи властивостями конденсаторів, опорів, дiодiв, транзисторів і т.ін. Досить найтонкішим металевим виведенням або просто " каналом зв'язку " усередині кристала з'єднати один його ділянка з іншими, що виконують ту або іншу функцію, та інтегральна схема замінює велике число різних деталей та дозволяє звільнитись від багатьох нестач напівпровідникових схем. Перехід на інтегральні схеми сприяв підвищенню якості ЕОМ, зменшенню їх габаритів та споживлюваної їми енергії. В чому ж основна різниця ЕОМ третього покоління від його попередників ?

ЕОМ третього покоління оперують довільно літерно-цифровою інформацією. В них фактично з'єдналось два напрямки попередніх поколінь машин: ЕОМ для ділового, комецiйного застосування з обробкою алфавітної інформації та ЕОМ, призначені для наукових створень i обробки цифрової інформації.

Змінився порядок роботи ЕОМ третього покоління; ці машини побудовані по принципу незалежної паралельної роботи різних їх пристроїв: процесорів, засобів зовнішньої пам'яті. Незалежну роботу пристроїв забезпечують канали, керовані спеціальним пристроїв, куди поступає інформація від користувачів ЕОМ. Це пристрій та здійснює первинну переробку інформації, звільнюючи основний пристрій від непродуктивної роботи.

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

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

2. Технічне завдання

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

а). Система числення - двійкова.

б). Форма представлення чисел - з плаваючою комою.

в). Розрядність - 24 розряди.

Мантиса - 17 розрядів.

Порядок - 7 розрядів.

Проілюструвати на числах: -11,43 та 121,937.

Розробити операційний автомат по отриманому алгоритму.

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

4. Описати технологію числового контролю операції множення, модуль 5 (кодовий).

3.Розробка машинного алгоритму операції

3.1 Основні способи виконання операції множення

Ми використовуємо двійкову систему числення, в якій використовується декілька основних способів виконання операції множення:

1. Множення, починаючи з молодших розрядів множника, зі зсувом множеного вліво.

Множник B = 0b₁b₂…b_n перетворюється по схемі Горнера

B = (…((b_n2^-1 + b_n-1)2^-1 + b_n-2)2^-1 + … + b₂)2^-1 + b₁)2^-1

Тоді C = AB = (…((b_n0,a₁a₂…a_n)2^-1 + b_n-10,a₁a₂…a_n)2^-1 +

+ … + b₁0,a₁a₂…a_n)2^-1 .

Тут множення починається з молодших розрядів та зсувається вправо сума часткових добутків. [6]

Структурну схему пристрою наведено на рис. 3.1.2. Час виконання операції можна визначити за формулою (3.2)

Т_мн2 = n t_дод (3.2)

Регістр множника повинен мати кола зсуву вправо, регістр множеного - кола зсуву вліво, а суматор часткових добутків не має кіл зсуву.

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

Рис 3.1.2.

2. Множення, починаючи з молодших розрядів із зсувом вправо суми часткових добутків.

Припустимо В-множене (В>0), A-множник (А>0) С-добуток. Тоді у випадку зображення чисел у формі з фіксованою комою отримуємо

А = а₁а₂…а_n ;

B = b₁b₂…b_n = b₁2^-1 + b₂2^-2 + … + b_n2^-n;

Звідси С = АВ = (0а₁а₂…а_n)(b₁2^-1 + … + b_n2^-n) =

= (2^-10,a₁a₂…a_n)b₁ + (2^-10,a₁a₂…a_n)b₂ + … +

+ (2^-n0,a₁a₂…a_n)b_n .

Множник 2^-n означає зсув на n розрядів вправо числа яке заключне в дужки тобто в даному випадку зсувається вправо множене і множення починається з старших розрядів. [6]

Структурну схему пристрою для множення, реалізуючого цей метод, наведено на рис. 3.1.1. Час виконання операції можна визначити за формулою (3.1).

Т_мн1 = n (t_дод + t_зс) (3.1)

Регістр множника і суматор часткових добутків повинні мати кола зсуву вправо. Регістр множеного може не мати кіл зсуву.

Рис 3.1.1.

При даному методі множення всі три регістри мають однакову довжину, яка дорівнює числу розрядів множників. Цей метод знайшов найбільше застосування в ЕОМ 3.

3. Множення, починаючи зі старших розрядів множника зі зсувом вліво суми часткових добутків.

Множник записується таким чином

B = 2^-n(b_n + b_n-12¹ + b_n-22² + … +b₁2^n-1) .

В цьому випадку

С = AB = 2^-n[b_n0,a₁a₂…a_n + b_n-1(2¹0,a₁a₂…a_n) +

+ b_n(2²0,a₁a₂…a_n) + … + b₁(2^n-10,a₁a₂…a_n)] .

Це означає що множення починається з молодших розрядів і множене зсувається вліво на один розряд в кожному такті. [6]

Структурну схему пристрою наведено на рис. 3.1.3. Час виконання операції визначається за формулою (3.3).

Т_мн3 = n (t_дод + t_зс) (3.3)

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

Рис 3.1.3.

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

4. Множення, починаючи із старших розрядів множника з сувом вправо множеного.

Якщо множник записати по схемі Горнера

B = 2^-n(…((b₁2¹ + b₂)2¹ + … + b_n-1)2¹ + b_n

То C = AB = 2^-n(…((b₁0,a₁a₂…a_n)2¹ + b₂0,a₁a₂…a_n)2¹ + … +

+ b_n-10,a₁a₂…a_n)2¹ + b_n0,a₁a₂…a_n) .

У цьому випадку множення починається з старшого розряду і в кожному такті зсувається вліво сума часткових добутків. [6]

Структурну схему наведено на рис 3.1.4. Час виконання операції можна визначити за формулою (3.4).

Т_мн4 = n t_дод (3.4)

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

Рис 3.1.4.

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

3.2 Множення чисел в прямому коді що представлені у формі з плаваючою комою, починаючи зі старших розрядів з групуванням розрядів множника

Для обробки чисел з плаваючою комою згідно з формулою (3.5)

AB = m_a2^Pam_b2^Pb = (m_am_b)2^(Pa+Pb) (3.5)

необхідно виконати такі дії

Множення мантис операндів.

Додавання порядків.

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

Корекція порядку.

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

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

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

До апаратних методів належать поділення множника на частини множення з запам'ятовуванням переносів та інші до логічних - пропуск тактів додавання у випадках коли чергова цифра множника нуль групування розрядів множника послідовне перетворення цифр множника.

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

Представлення двійкових чисел за допомогою трьох цифр є неоднозначним тому з усіх можливих варіантів вибирають той що містить найменшу кількість значущих цифр тобто 1 і -1. Для цього групу з m>2 одиниць 011…10 преобразують в групу 100…-10. У правомірності таких перетворень легко переконатися на такому прикладі.

30₍₁₀₎ = 011110₍₂₎ = 02⁵ + 12⁴ + 12³ + 12² + 12¹ +02⁰ =

= 12⁵ + 02⁴ + 02³ + 02² + (-1)2¹ + 02⁰ = 32₍₁₀₎ - 2₍₁₀₎ =1000(-1)0₍₂₎ .

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

Особливість множення з групуванням розрядів множника заключається в аналізі сусідніх розрядів множника. Аналізу піддаються дві стасші цифри двох сусідніх пар--поточної і сусідньої молодшої. Перетворюються пари 11=100-01 і 10=100-10. Кожна перетворена пара формується з трьох доданків:

А) числа, утвореного цифрами пари, що перетворюється;

Б) числа -100, якщо в старшому розряді 1 (інакше цей доданок дорівнює 0);

В) числа +1, якщо в старшому розряді сусідньої молодшої пари 1 (інакше цей доданок дорівнює 0);

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

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

3.3 Розробка алгоритму та операційного автомату

В функціональному та структурному вiдношеннi операційний пристрiй подiляеться на дві частини: операційний та управляючий автомати. Операційний автомат ОА служить для збереження слів iнформацiї, виконання набору мiкрооперацiй i обчислення значень логічних умов, тобто операційний автомат є структурою, організованою для виконання дій над iнформацiєю. Мiкрооперацiї, що реалізуються операційним автоматом, iнiцiюються множиною управляючих сигналів Y=[y(1),...,y(m)], з кожним iз них ототожнюється визначена мiкрооперацiя. Значення логічних умов, які обчислюються в операційному автоматі, відображаються множиною освiдомлюючих сигналів X=[x(1),...,x(l)], кожний з яких ототожнюється з визначеною логічною умовою. Управляючий автомат УА генерує послiдовнiсть управляючих сигналів, визначену мiкропрограмою, яка вiдповiдає значенням логiчних умов. iнакше говорячи, управляючий автомат задає порядок виконання дiй в операцiйному автоматi, що зрозумiло з алгоритму виконання операцiй. Найменування операцiї, яку необхiдно виконати в пристрої, визначаеться кодом g операцiї. По вiдношенню до управляючого автомата сигнали g(1),...,g(h), за допомогою яких кодується найменування операцiї, i освiдомлюючi сигнали x(1),...,x(l), що формуються в операцiйному автоматi, грають однакову роль: вони впливають на порядок утворення робочих сигналів Y. Тому сигнали g(1),...,g(h) i x(1),...,x(l) вiдносяться до одного класу - класу освiдомлюючих сигналiв, що iдуть на вхiд управляючого автомату.

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

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

Функцiя операцiйного автомату визначається слiдуючою єднiстю вiдомостей:

1. Множиною вхiдних слiв d={d(1),...,d(H)}, що вводиться в автомат в якостi операндiв.

2. Множиною вихiдних слiв R={r(1),...,r(Q)}, що представляє результати операцiй.

3. Множиною мiкрооперацiй Y={y(m)}, m=1,...,M, реалiзуючих перетворення S={f(m)}(S) над словами iнформацiї, де f(m) - шукана функцiя.

Таким чином, функцiя операцiйного автомату задана, якщо визначенi множини D,R,S,Y,X. Час не є аргументом функцiї операцiйного автомату. Функцiя встановлює список дiй - мiкрооперацiй i логiчних умов,- якi може виконувати автомат, але нiяк не визначає порядок слiдування цих дiй у часi. Iнакше говорячи, функцiя операцiйного автомату характеризує засоби, якi можуть бути використанi для обчислень, але не сам обчислювальний процес. Порядок виконання дiй у часi визначається у формi функцiй управляючого автомату.

Функцiя управляючого автомату - це операторна схема алгоритму (мiкропрограми ), функцiональними опраторами якої є символи y(1),...,y(m), ототожнюванi з мiкрооперацiями, i в якостi логiчних умов ( предикатiв ) використовуються бульовi змiннi x(1),...,x(l). Операторна схема алгоритма найбiльш часто представляеться у виглядi граф-схеми або логiчноi схеми алгоритму. Кожна з цих форм визначнає обчислювальний процес у послiдовному аспектi - втсановлює порядок перевiрки логiчних умов x(1),...,x(l) i порядок черги мiкрооперацiй y(1),...,y(m).

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

Для реалізації множення з перетворенням цифр множника (множення чисел виконується з плаваючою комою) потрібні такі вузли

Вхідні дані (множене та множник) надходять в пристрій через шину вхідних даних Ш_вх .

Результат (добуток) видається з пристрою через шину вихідних даних Ш_вих.

Для зберігання операндів потрібні регістри мантиси А (Рг Ам) мантиси В (Рг Вм) порядку А (Рг Ап) та порядку В (Рг Вп).

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

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

Для підраховування кількості кроків множення використовується лічильник (Ліч).

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

3.4 Алгоритм

Із вхідної шини в регістри Рг Ам і Рг Вм поступають прямі коди відповідно множеного і множника.

Із вхідної шини в регістри Рг Ап і Рг Вп поступають розряди множеного і множника.

В лічильник заноситься розрядність операндів. Суматори СМм і СМп зануляються.

Далі перевіряємо операнди на рівність нулю. Якщо хоча б один із них = 0, то операція закінчується.

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

Аналізуємо три старших розряди множника: а) якщо вони = 000, пропускаємо такт множення і здійснюємо лише зсув на два розряди, зменшуємо лічильник на 1; б) якщо вони = 001, додаємо на суматорі вміст Рг Ам, робимо зсув на два розряди Рг Вм і СМм, зменшуємо лічильник на 1; в) якщо вони = 010, додаємо на суматорі вміст Рг Ам, робимо зсув на два розряди Рг Вм і СМм, зменшуємо лічильник на 1; г) якщо вони = 011, додаємо на суматорі 2*Рг Ам, робимо зсув на два розряди Рг Вм і СМм, зменшуємо лічильник на 1; д) якщо вони = 100, додаємо на суматорі (не)2*Рг Ам, робимо зсув на два розряди Рг Вм і СМм, зменшуємо лічильник на 1; е) якщо вони = 101, додаємо на суматорі вміст (не)2*Рг Ам+1, робимо зсув на два розряди Рг Вм і СМм, зменшуємо лічильник на 1; є) якщо вони = 110, додаємо на суматорі (не)Рг Ам, робимо зсув на два розряди Рг Вм і СМм, зменшуємо лічильник на 1; ж) якщо вони = 111, додаємо на суматорі (не)Рг Ам+1, робимо зсув на два розряди Рг Вм і СМм, зменшуємо лічильник на 1;

Перевірка лічильника на рівність нулю. Якщо Ліч 0, то переходим до пункту 6. Якщо Ліч = 0, то п. 8

Далі іде перевірка на порушення нормалізації. Порівнюєм СМм[0] і СМм[1]. Якщо вони рівні, то п. 10.

Якщо СМм[0] і СМм[1] різні, то нормалізуємо мантису результату.

На шину виходу Шдвих передаються результати операції із суматорів СМм і СМп, на цьому виконання операції завершується.

A0	Y1	Рг Ам :=Шдвх
	Y2	Рг Ап :=Шдвх
A1	Y3	Рг Вм :=Шдвх
	Y4	Рг Вп :=Шдвх
A2	Y5	СМм :=0
	Y6	СМп :=0
	Y7	Ліч :=9
	X1	Рг Ам =0
A3	X2	Рг Вм =0
A4	Y8	СМп := СМп + Рг Ап
A5	Y9	СМп := СМп + Рг Вп
A6	X4	Рг Вм [1]
A7	X4	Рг Вм [1]
A8	X5	Рг Вм [2]
A9	X5	Рг Вм [2]
A10	X5	Рг Вм [2]
A11	X5	Рг Вм [2]
A12	Y10	СМм := СМм + Рг Ам
A13	Y11	СМм := СМм + 2*Рг Ам
A14	Y13	СМм := СМм + 2*(не)Рг Ам
A15	Y12	СМм := СМм + 2*(не)Рг Ам +1
A16	Y15	СМм := СМм + (не)Рг Ам
A17	Y14	СМм := СМм + (не)Рг Ам +1
A18	Y16	СМм := R(2,СМм)
	Y17	Рг Вм := L(2,Рг Вм)
	Y18	Ліч :=Ліч-1
A19	X6	Ліч=0
A20	X7	СМм[0]= СМм[1]
A21	Y19	СМм := R(1,СМм)
	Y20	СМп :=СМп +1
A22	Y21	Шдвих :=СМм
	Y22	Шдвих :=СМп
A23	X3	Рг Вм [0]

3.5 Приклад

Тепер розглянемо дію цього алгоритму на прикладі множення конкретних чисел: -11,43 і 121,937

-11,43(10) = 1,101100101001100(2) р=-2

121,937(10) = 0,11101110001010001(2) р=3

Похибка при переводі з десяткової у двійкову систему числення буде дорівнювати вазі молодшого розряду, тобто 1/2¹⁶ = 1/65536 = 1,5258789062510^-5.

Коди цих чисел: А =11,101100101001100; В=00,11101110001010001

Виконаємо множення цих чисел за розробленим алгоритмом:

На початковому етапі СМм=0

І група розрядів множника = 011

0000000000000000000000000000000

10110010100110_________________

1011001010011000000000000000000

ІІ група розрядів множника = 110

1011001010011000000000000000000

__01001101011001_______________

1010001011111000100000000000000

ІІІ група розрядів множника = 011

1010001011111000100000000000000

____10100010100110_____________

1010010100100011000000000000000

ІV група розрядів множника = 110

1010010100100011000000000000000

______01001101011001___________

1010011001011000100100000000000

V група розрядів множника = 000, робимо лише зсув

VІ група розрядів множника = 010

1010011001011000100100000000000

__________10110010100110_______

1010011001100101001101100000000

VІІ група розрядів множника = 000, робимо лише зсув

VІІІ група розрядів множника = 010

1010011001100101001101100000000

______________101100101001100__

1010011001100101100111000110000

ІХ група розрядів множника = 001

1010011001100101100111000110000

________________101100101010110

1010011001100101101001101000110

отримано результат множення.

Переведемо отриманий результат в десяткову систему числення:

0(2⁰) + 1(2¹) + 1(2²) + 0(2³) + 0(2⁴) + 0(2⁵) + 0(2⁶) + 1(2⁷) + 0(2⁸) + 0(2⁹) + 0(2¹⁰) + 1(2¹¹) + 0(2¹²) + 0(2¹³) + 1(2¹⁴) + 1(2¹⁵) + 0(2¹⁶) + 1(2¹⁷) + 0(2¹⁸) + 0(2¹⁹) + 1(2²⁰) + 0(2²¹) + 0(2²²) + 0(2²³) + 1(2²⁴) + 1(2²⁵) + 0(2²⁶) + 0(2²⁷) + 1(2²⁸) + 1(2²⁹) = 2+4+128+2048+16384+32768+131072+1048576+16777216+33554432+

+268435456+1073741824=1393739900

з урахуванням розрядів маємо: 1393,7399.

При множенні даних чисел в десятковій системі числення було отримано

1393,73991; таким чином 1393,7399 1393,73991 тобто похибка зовсім незначна і дорівнює 0,00001.

Множення за даним алгоритмом виконалось правильно, отже алгоритм був розроблений вірно.

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

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

Числовий метод контролю.

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

r_A=A-{A/p}p,

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

Величина модуля р істотно впливає на якість контролю, що проводиться; якщо р=q ( q - основа системи числення, в якій виражене число) і має місце числовий контроль, то контролюється тільки молодший розряд числа і контроль як такий не має змісту; Для р = q^m вірні аналогічні міркування, так як, якщо m<n, знову ж не всі розряди числа приймають участь у контролі і помилки в розрядах старших m взагалі не сприймаються.

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

А r_A (modp); B r_B (modp) де 0 r_A p-1,

то А + В r_A+ r_B(modp).

Звідси r_{A + В} r_A + r_B(modp).

Аналогічним чином доводиться вірність і слідуючих відношень

r_{A -В} r_A - r_B(modp).

r_{A В} r_A r_B(modp).

Виконаємо числовий контроль виконання операції множення по модулю 5 для заданих чисел

r_A = 43 (mod 5)= 3(mod 5)

r_B = 234 (mod 5)= 4(mod 5)

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

r_A+ r_В = 3+4 (mod 5) = 2(mod 5).

r_А+B = 277 (mod 5) = 2(mod 5)

r_{A - В} = 3-4 (mod 5) = 1(mod 5).

r_{A -} r_В = 191 (mod 5) = 1(mod 5).

r_{A * В} = 3*4 (mod 5) = 2(mod 5).

r_{A *} r_В = 10062 (mod 5) = 2(mod 5).

Результат r_A = 3 r_B = 4 r_{A +В} = 2 r_{A -} r_В = 1 r_{A *} r_В = 2.

5. Синтез керуючого автомату

Керуючий автомат (КА) генерує послідовність керуючих сигналів, яка передбачена мікропрограмою і відповідає значенням логічних умов. Інакше кажучи, керуючий автомат задає порядок виконання дій в операційному автоматі, який виходить з алгоритму виконання операцій. Найменування операції, яку необхідно виконувати у пристрої, визначається кодом операції. По відношенню до керуючого автомату сигнали коду операції, за допомогою яких кодується найменування операції, і повідомлювальні сигнали х₁,...,х_l, які формуються в операційному автоматі, грають однакову роль: вони впливають на порядок генерування керуючих сигналів y. Тому сигнали коду операції і умовні сигнали відносяться до одного класу - до класу повідомлювальних сигналів, які поступають на вхід керуючого автомату.

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

В залежності від способу визначення вихідного сигналу в керуючих автоматах розрізняють три типи абстрактних автоматів: автомат Мілі, автомат Мура, С-автомат. В абстрактному автоматі Мілі функція виходів задає відображення (XxS)Y. В абстрактному автоматі Мура функція виходів задає відображення SY. В абстрактному С-автоматі вводяться дві функції виходів ₁ і ₂, що задають відображення (XxS)Y₁ і SY₂ відповідно. При цьому алфавіт виходів С-автомата, Y=Y₁=Y₂ або Y=Y₁Y₂.

Довільний абстрактний атомат Мілі або Мура має один вхідний і один вихідний канали. Довільний абстрактний С-автомат має один вхідний і два вихідних канали 2.

Адресація мікрокоманд

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

Примусова адресація мікрокоманд.

Примусова адресація зводиться до вказання в кожній мікрокоманді адреси наступної мікрокоманди. Адреса слідуючої визначається в залежності від коду Х та значення хх або полем А0 чи полем А1.

З метою скорочення довжини мікрокоманди для формування адреси наступної мікрокоманди відводиться єдине поле А. Якщо поле Р=0, то значення А, безумовно визначає адресу наступної мікрокоманди. Якщо Р = 1, то адреса наступної мікрокоманди дорівнює (А + хх), де х - значення логічної умови з номером Х. В результаті цього реалізується умовний перехід: якщо х=0, то до мікрокоманди з адресою А; якщо х=1, то до мікрокоманди з адресою (А+1). Адреса виконання А1 = А + х формується лічильником комбінаційного типу. Скорочення довжини слова ПЗП на р двійкрвих розрядів знижує вартість ПЗП на (р/k) С( P, k), де С( P, k) - вартість ПЗП ємністю Р k - розрядних слів.

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

Безпосередня адресація мікрокоманд.

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

Після виконання мікрокоманди з адресою А може виникнути необхідність в переході до мікрокоманди з адреси В = А + 1. Перехід може бути безумовним або залежати від поточного значення х. Умовні переходи реалізуються слідуючим чином: якщо х = 0, то виконується наступна мікрооперація з адресою (А + 1); якщо х = 1, то наступною виконується мікрокоманда з адресою В. Для реалізації умовних переходів в мікрокоманду вводиться адресна часна частина, яка складається з полів Х та В.

При безпосередній адресації, як правило, використовуються мікрокоманди двох типів: операційні та керуючі. Операційна мікрокоманда задає набір операцій Y1, Y2, ...,Yн і неявно рахує адресу наступної мікрокоманди рівною (А + 1). Керуючі мікрокоманди використовуються для зміни природнього порядку проходження мікрокоманд, що зводиться до виконання умовних та безумовних переходів. Керуюча мікрокоманда містить поле Х, яке визначає номер логічної умови, і поле В, яке визначає адресу наступної мікрокоманди. Якщо Х = 0, то адреса наступної мікрокоманди безумовно дорівнює В. Для виділення операційних і керуючих мікрокоманд в керуючому слові вводиться поле ознаки, що визначає тип мікрокоманди: якщо Р = 1, то мікрокоманда являється операційною; якщо Р = 1 - керуючою.

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

Автомат повинен мати 23 стани (а0 - а23). Закодуємо всі стани автомату та керуючі сигнали:

6. Заключення

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

В ході курсової роботи проведено аналіз проблеми логічної реалізації операції множення чисел в прямому коді що представлені у формі з плаваючою комою, починаючи зі старших розрядів з групуванням розрядів множника, вище вказана операція перевірена на прикладі чисел А=-11,43 та В=121,937. Тобто ми освоїли основні закони, які потрібні для логічної організації різних операцій.

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

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

7. Література

1. Каган Б. М. «Электронные вычислительные машины и системы». Москва Энергоатомиздат 1991 с.592

2. Конспект лекцій по ПТЦА.

3. Лужецький А. В., Білан С. М., Квітка М. А. Прикладна теорія цифрових автоматів. Методичні вказівки. - Вінниця, ВДТУ, 1997 - 56 с. Укр. мовою.

4. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов.- Мн.:Высшая школа, 1980 г.

5. Майоров С. А. «Структура электронных вычислительных машин». Ленинград «Машиностроение» 1979г. с.384

6. Савельев А. Я. «Прикладная теория цифровых автоматов» Москва «Высшая школа» с. 269

7. Самофалов К.Г., Корнейчук В.И., Тарасенко В.П. Цифровые ЭВМ.- Киев:Высшая школа, 1989 г.

8. Стахов А. П. Коды золотой пропорции. - М.:”Радио и связь”, 1984. - 152 с., ил. - (кибернетика)