Курсовий проект на тему:

«Розробка операційного та керуючого автомату, що виконує операцію прискореного множення»

Вступ

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

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

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

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

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

1.1 Метод виконання операції прискореного множення

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

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

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

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

1) Прискорення за рахунок заміни комбінацій цифр. Наприклад: комбінації 00, 01 і 10 не перетворюються, а комбінація 11 замінюється на 01 і 1 йде в наступний розряд. При виконані множення, якщо в деякому розряді множника знаходиться 1, то до суми часткових добутків додається множене з відповідним зсувом, а якщо 1, то до суми часткових добутків додається доповняльний код множеного з відповідним зсувом.

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

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

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

Множимо числа з фіксованою комою в доповняльному коді. Множення виконується з врахуванням знакового розряду, якщо В>0 то виконуємо множення, якщо В<0 то робимо корегуючі дії: додаємо доповнений код числа А. Додаємо також ще два часткові добутки (з врахуванням зсуву) без розповсюдження переносу і формуємо проміжну суму і проміжний перенос.

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

Останній крок: додавання з розповсюдженням переносу проміжної суми та проміжного переносу.

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

1.2 Розробка алгоритму

Початок

СМ:= 0;

Рг1:=0;

Рг2:=0;

Рг3:=0;

РгВ:=В_доп;

РгА[0:8]:=A_доп;

n:=8;

РгВ[0]=1

Рг1:=А_доп

0

РгА:=R₁[РгA]

РгВ[1]=1

Рг2:=А_доп

РгА:=R₁[РгA]

РгВ[2]=1

Рг3:=А_доп

0

РгА:=R₁[РгA]

1.

1

1

1

Згідно обраного методу виконання множення побудуємо блок схему алгоритму:

0

Кінець

0

1.

CM:=Рг1+Рг2+Рг3

Формуемо проміжну суму і проміжний перенос Р

РгВ:=L₂[РгВ]

n:=n-2

k = n

1

РгВ[1]=1

CM:=CМ+Р+РгА

Формуемо проміжну суму і проміжний перенос Р

0

CM:=СМ+Р

Формуемо проміжну суму і проміжний перенос Р

РгА:=R₁[РгA]

РгВ:=L₁[РгВ]

n:=n-1

1

СМ:=СМ+Р

1

РгВ[1]=1

0

СМ:=СМ+1

Описання блок-схеми алгоритму

Спочатку виконуємо ініціалізацію:

• в суматор заносимо 0;

• в регістр Рг1 заносимо 0;

• в регістр Рг2 заносимо 0;

• в регістр Рг3 заносимо 0;

• в лічильник n заносимо 8;

• у перші 8 розрядів регістра РгА заносимо доповняльний код числа А;

• в регістр РгВ заносимо доповняльний код числа В;

Перевіряємо знак числа В (РгВ[0]), якщо він рівний 1 (від’ємне) то в

регістр Рг1 заносимо доповняльний код числа А. Зсуваємо регістр РгА вправо на один розряд. Дивимося на старший розряд числа В (РгВ[1]), якщо там 1 то заносимо в регістр Рг2 значення регістра РгА (першій частковий добуток). Зсуваємо регістр РгА вправо на один розряд. Дивимося на другий розряд числа В (РгВ[2]), якщо там 1 то заносимо в регістр Рг3 значення регістра РгА (другий частковий добуток). Зсуваємо регістр РгА вправо на один розряд. Додаємо в суматорі значення з регіс-трів Рг1, Рг2, Рг3 та формуємо проміжну суму та проміжний перенос Р. Зсуваємо регістр РгВ вліво на два розряди. Зменшуємо значення лічильника на 2.

Далі починаємо цикл:

Поки n не дорівнює 0 дивимося на старший розряд числа В (РгВ[1]), якщо там одиниця додаємо до суматора (попередня проміжної суми) вміст регістра РгА (черговий частковий добуток) та попередній проміжний перенос Р, якщо ж 0, то додаємо лише попередній проміжний перенос Р; формуємо чергову проміжну суму та проміжний перенос. Зсуваємо регістр РгА вправо на один розряд. Зсуваємо регістр РгВ вліво на один розряд. Зменшуємо значення лічильника на 1. Повторюємо цикл.

Після закінчення циклу додаємо до суматора (останньої проміжної суми), з розповсюдженням переносу, останній проміжний перенос Р. Дивимося на знак результату (СМ[0]), якщо там 1 (результат від’ємний), перетворюємо доповняльний код в прямий: інвертуємо суматор і додаємо 1. Операцію множення виконано результат знаходиться в суматорі.

1.3 Приклад множення

Візьмемо для прикладу помноження два числа:

A=0,69140625 та B= -0,80078125.

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

А₂=0.10110001; А_доп=0.10110001;

В₂=1.11001101; В_доп=1.00110011.

Розглянемо приклад помноження цих чисел, за допомогою алгоритму:

СМ

РгB

ПРИМІТКИ

0.0000000000000000

1.01001111

+0.000000000

0.0000000000

1.00110011

1.110011_ _

1.10011_ _ _

1.0011_ _ _ _

1.011_ _ _ _ _

1.11_ _ _ _ _ _

1.1_ _ _ _ _ _ _

СM:=0;

Рг1:=А_доп;

СМ:=Рг1+Рг2+Рг3;

1.0100111100000000 +0.0000000000000000

0.00010110001

форм. пром. суму і пер. Р

РгВ2; РгА1;

СМ:=СМ+РгА+Р;

1.0101100100100000

+0.0000110000000000

0.000010110001

форм. пром. суму і пер. Р

РгВ1; РгА1;

СМ:=СМ+РгА+Р;

1.0101111000110000

+0.0001001000000000

0.0000000000000

форм. пром. суму і пер. Р

РгВ1; РгА1;

СМ:=СМ+Р;

1.0100110000110000

+0.0010010000000000

0.00000000000000

форм. пром. суму і пер. Р

РгВ1; РгА1;

СМ:=СМ+Р;

1.0110100000110000

+0.0000100000000000

0.000000010110001

форм. пром. суму і пер. Р

РгВ1; РгА1;

СМ:=СМ+РгА+Р;

1.0110000101010010

+0.0001000001000000

0.0000000010110001

форм. пром. суму і пер. Р

РгВ1; РгА1;

СМ:=СМ+РгА+Р;

1.0111000110100011

⁺0.0000000010100000

СМ:=СМ+Р;

1.0111001001000011

1.1000110110111101

СМ:=СМ+1;

В результаті отримали відповідь:

А*В=1.1000110110111101₂= – 0,553665161133;

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

2.1 Теоретичні відомості

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

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

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

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

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

Розрізняється два типи автоматів: Мура і Мілі. Мура простіший в розумінні, Мілі – складніший, при реалізації – навпаки. У Мура Вихідні сигнали пов’язані тільки зі станами, для Мілі вихідні сигнали залежать як від станів, так і від вхідних сигналів.

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

2.2 Розробка алгоритму роботи автомату

Початок

Y₁

a₁

X₁

Y₂

0

Y₃

X₂

Y₄

Y₃

X₃

Y₅

0

Y₃

1.

1

1

1

0

a₃

a₂

a₆

a₇

a₅

a₄

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

Кінець

0

1.

Y₆

Y₇

Y₈

X₄

1

X₂

Y₉

0

Y₁₀

Y₃

Y₁₁

Y₁₂

1

Y₁₃

1

X₅

0

Y₁₄

Y₁₅

a₁₀

a₁

a₉

a₈

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

Через Y позначимо операції, якщо зустрічаються однакові операції, то вони теж позначаються однаково. Якщо між операціями немає умовної вершини то їх об’єднуємо в одну операційну вершину і між ними не ставиться стан. Кількість розставлених станів дорівнює 10, для їх кодування використаємо 4 двійкових розрядів.

2.3 Побудова графа автомата

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

a₁₀

a₁

a₃

a₂

a₄

a₅

a₆

a₇

a₉

a₈

Y₃

Y₁

Х₁Y₂

Х₁Y₃

Y₃

Х₂Y₄

Х₂Y₃

Х₃Y₁₅

Х₃Y₁₄

Х₄Y₁₃

Х₃Y₅

Х₄ Х₂Y₉

Х₃ Y₃Y₆Y₇Y₈

Y₃Y₆Y₇Y₈

Y₃Y₁₁Y₇

Х₄ Х₂Y₉

2.4 Побудова таблиці функціонування

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

Автомат вказаний на графі має 10 станів, для їх кодування використовуємо 4 двійкових розряди, тому потрібно 4 тригера. Закодуємо стани автомата таким чином: а₁ = 0001, а₂ = 0010, а₃ = 0011, а₄ =0100, а₅ = 0101, а₆ = 0110, а₇= 0111, а₈ = 1000, а₉ = 1001, а₁₀ = 1001.

Попередній

стан

Код

Т₄Т₃Т₂Т₁

Наступний

стан

Код

Т₄Т₃Т₂Т₁

Вхідні

сигнали

Вихідні

сигнали

a₁₀

1010

a₁

0001

X₅

X₅

Y₁₄

Y₁₅

a₁

0001

a₂

0010

Y₁

a₂

0010

a₃

0011

X₁

Y₂

a₂

a₃

0010

0011

a₄

0100

X₁

Y₃

Y₃

a₄

0100

a₅

0101

X₂

Y₄

a₄

a₅

0100

0101

a₆

0110

X₂

Y₃

Y₃

a₆

0110

a₇

0111

X₃

Y₅

a₆

a₇

a₉

0110

0111

1001

a₈

1000

X₃

Y₃ Y₆ Y₇ Y₈

Y₃ Y₆ Y₇ Y₈

Y₃ Y₁₁ Y₁₂

a₈

1000

a₉

1001

X₄ X₂

X₄ X₂

Y₉

Y₁₀

a₈

1000

a₁₀

1010

X₄

Y₁₃

2.5 Синтез схеми керуючого автомату

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

Для вхідних сигналів:

D_T1 = a₁₀ + a₂ x₁ + a₄ x₂ + a₆x₃ + a₈x_4;

D_T2 = a₁ + a₂ x₁ + a₄ x₂+ a₅ + a₆x₃ + a₈ x₄;

D_T3 = a₂ x₁ + a₃ + a₄ +a₅ + a₆x₃;

D_T4 = a₇ + a₆x₃ + a₉+ a₈;

Для вихідних сигналів:

y₁ = a₁;

y₂ = a₂x₁;

y₃ = a₂x₁+a₃+a₄x₂+a₅+a₆x₃+a₇+a₉;

y₄ = a₄x₂;

y₅ = a₆x₃;

y₆ =a₆x₃+a₇;

y₇ = a₆x₃+a₇;

y₈ = a₆x₃+a₇;

y₉ = a₈x₄x₂;

y₁₀= a₈x₄x₂;

y₁₁= a₉;

y₁₂= a₉;

y₁₃= a₈x₄;

y₁₄= a₁₀x₅;

y₁₅= a₁₀x₅.

На основі цих рівнянь синтезуємо схему керуючого автомату. Для зручності побудови використаємо шину. Оскільки автомат має 10 станів, для кодування яких потрібно 4 двійкових розряди то для побудови схеми використаємо 4 D-тригера з керуючими тактовими входами.

2.6 Побудова структурної схеми автомату

Побудуємо також структурну схему автомату:

0 1 РГ А ¹ 16

0 1 РГ B ^{2 1} 8

0 1 СМ 16

0 1 РГ 3 16

0 1 РГ 2 16

0 1 РГ1 16

1 n 8

Y1

Y1

Х₁

А_доп

В_доп

Y1

Y2

Y4

Y5

Y3

Y6

Y1

Y8

Y12

Y9

Y13

Y10

Y11

Y7

Y14

Х₂

Х₃

Х₅

Висновок

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

У першому розділ курсової роботи було розроблено алгоритм виконання вказаної операції над числами.

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

Використана література

1. А.Я. Савльев «Прикладна теория цифрових автоматів» – Москва В. Шк. – 1987.

2. Методичні вказівки до вивчення курсу «Прикладна теорія цифрових автоматів» – Вінниця ВДТУ-1997.

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

4. Методические указания к практическим занятиям по курсу «Теория и проектирование ЦВМ» – Винница ВПИ - 1982.

5. К.Г. Самофалов «Цифровые ЭВМ» – ВШ – 1989.