Размещено на http://www.allbest.ru/

Вступ

Перші ЕОМ з програмованим керуванням із програмою, яка зберігається в пам'яті з'явились практично одночасно в Англії, США та ін.

Фундаментальний внесок в розвиток вітчизняної обчислювальної техніки вніс академік С.А. Лєбєдєв. Під його керівництвом в 1949-1951 роках в АНУРСР в Києві була побудована перша в нашій країні ЕОМ - мала електронна лічильна машина (МЕЛМ), а в 1952-1954 рр. - швидкодіюча електронна лічильна машина (ШЕЛМ), яка виконувала 8000 операцій/сек. і була на той час однією із самих швидкодіючих ЕОМ в світі.

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

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

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

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

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

1.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

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

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

Рисунок 1.1 - Структурна схема пристрою множення (метод 1).

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

Метод 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 розрядів вправо числа яке заключене в дужки тобто в даному випадку зсувається вправо множене і множення починається з старших розрядів.

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

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

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



Рисунок 1.2 - Структурна схема пристрою множення (метод 2)

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

Метод 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)].

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

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

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



Рисунок 1.2 - Структурна схема пристрою множення (метод 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).

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

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

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

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



Рисунок 1.4 - Структурна схема пристрою множення (метод 4).

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

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

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

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

Аналізуємо пара розрядів	Перенос із попередньої пари розрядів	Перетворена пара розрядів	Примітка
00	0	00
01	0	01
10	0	10	Попередній зсув множника
11	0	0	1 для наступного розряду
00	1	01
01	1	10	Попередній зсув множника
10	1	0	1 для наступного розряду
11	1	00

Розглянемо докладніше метод групування розрядів множника. Розбивання множника на групи з довжиною 2 з цього слідує що ми переходимо до нової системи числення з основою 2². комбінації вигляду 01, 10 не змінюються, перетворюється 11 в наступну комбінацію 101. Для більш детального зображення побудуємо таблицю правила перетворення множника для системи (0,1,).

1.3 Формалізований опис операційного автомату

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

,

де

DI - множина вхідних даних,

S - множина проміжних результатів,

DO - множина вихідних даних,

X - множина логічних умов,

Y - множина мікрооперацій, що виконується,

Множиною вхідних даних є значення числа А, значення числа В, кількість розрядів n:

.

Множина проміжних результатів має вигляд:

.

Множиною вихідних даних є значення числа С:

.

Множина логічних умов має вигляд:

, де

х₁, х₂, х₃ - чергові цифри множника;

х₄ - логічна умова: якщо усі кроки множення виконані, то , інакше .

Множина мікрооперацій, що виконується:

.

1.4 Структурна схема операційного автомату

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

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

2. Для зберігання операнду А потрібний регістр (РгА). Для регістру А потрібна схема формування оберненого коду (СхФОК).

3. Для зберігання знаку операнда А потрібний регістр (Тзн А).

4. Для зберігання знаку операнда В потрібний регістр (Тзн В).

5. Для регістру А потрібна схема формування оберненого коду (СхЗс).

6. Для зберігання операнду В потрібний регістр (РгВ).

7. Для накопичення часткових добутків необхідно використати комбінаційний суматор (КСМ).

8. Для збереження результату потрібен регістр (РгС).

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

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

Структурна схема операційного автомата.

1.5 Машинний алгоритм виконання операції

Число А зі знаком записується в регістр Рг А і Тзн А, відповідно.

Число В зі знаком записується в регістр РгВ і Тзн В, відповідно.

Регістру С присвоюється значення 0.

Лічильнику присвоюється значення 8.

Розраховується знаковий розряд.

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

В=00 переходиться до пункту 11.

В=01 до регістру С додається значення регістр А.

В=10 до регістру С додається значення регістр А в доповняльному коді.

В=11 до регістру С додається зсунений на один розряд значення регістру А.

11. Зсувається регістр С вліво на 2 розряди.

12. Зсувається регістр В вліво на 2 розряди.

13. Вміст лічильника зменшується на 1.

14. Аналізується лічильник якщо він дорівнює 1, то потрібно перейти до пункту 15, інакше в п. 6.

15. Видається результат знак РгС на шину даних.

16. Видається результат РгС на шину даних.

17. Кінець алгоритму



Граф-схема алгоритму

1.6 Приклад реалізації алгоритму

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

Двійкові коди чисел А і В

Число А=0.458110	Число В=0,789110
Виконувані дії	Остача	Виконувані дії	Розряд
0.4581 · 2 = 0.9162 0.9162 · 2 = 1.8324 0.8324 · 2 = 1.6648 0.6648 · 2 = 1.3296 0.3296 · 2 = 0.6592 0.6592 · 2 = 1.3184	0 1 1 1 0 1	0.7891 · 2 = 1.5782 0.5782 · 2 = 1.1564 0.1564 · 2 = 0.3128 0.3128· 2 = 1.6256 0.6259 · 2 = 1.2512 0.2512· 2 = 0.5024	1 1 0 0 1 0
Отриманий код: 011101	Отриманий код: 110010

Двійковий код чисел

А = -0,4581= -0,0111011₂

В = -0,7891= -0,1100100₂

Запишемо машинне зображення операндів в прямому коді.

РгА= 0,0111011

РгВ= 1,000100

Виконаємо множення (вміст регістрів і виконані операції приведені в таб 2:

Приклад виконання множення за розробленим алгоритмом

РгС	РгВ	Примітки
0000000000000000	0,1100100	РгВ=В; РгC:=0
0,011101 + 1111000	1,001000	Х1=0; Х2=1 РгC:= РгC+РгА РгВ:=L2 (РгВ); РгC:=L2 (РгC)
0010101110 + 0000000111	0,100000	Х1=1; Х2=0 РгC:= РгC+(РгА) д РгВ:=L2 (РгВ); РгC:=L2 (РгC)
001011010101	0000000	Х1=0; Х2=1 РгВ:=L2 (РгВ); РгC:=L2 (РгC)

Sgn A + Sgn B= Sgn C

Знак дорівнє 1, тобто мінус

1.7 Обчислення абсолютної та відносної похибок виконання операції

0,7891*0,4581=0,36148 в десятковій.

0,011101

0,110010

011101

011101

011101

0,010110101010 множення в двійковій в стовпчик

0,3437- в десятковій

Абсолютна похибка ?=0,3614-0,3437=0,0177

Відносна похибка у=?/0,3437*100%=5,1%

2. Розробка керуючого автомату

2.1 Керуючі автомати з жорсткою логікою

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

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

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

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

Розмічена граф-схема алгоритму

2. Закодуємо вхідні та вихідні сигнали та стани автомату

3. Складаємо кодовану таблицю переходів та виходів.

xi	ai(t)	ai (t+1)	yi	D1	D2	D3	D4
-	a0	a1	y1	0	0	0	1
-	a1	a2	y2	0	0	1	0
-	a2	a3	y3	0	0	1	1
-	a3	a4	y4	0	1	0	0
-	a4	a5	y5	0	1	0	1
	a5	a6	-	0	1	1	0
	a5	a6	y6	0	1	1	0
	a5	a6	y7	0	1	1	0
	a5	a6	y8	0	1	1	0
-	a6	a7	y9	0	1	1	1
-	a7	a8	y10	1	0	0	0
-	a8	a9	y11	1	0	0	1
	a9	a10	y12	1	0	1	0
	a9	a6	-	0	1	1	0
	a9	a6	y6	0	1	1	0
	a9	a6	y7	0	1	1	0
	a9	a6	y8	0	1	1	0
-	a10	a0	y13	0	0	0	0

До складу керуючого автомату входять такі основні вузли:

- чотири D-тригерів для формування коду внутрішнього стану;

- дишифратор DC для визначення стану за його двійковим кодом;

- логічні схеми на елементах «І», «АБО», «НІ».

3. Методика контролю арифметичної операції

3.1 Загальні теоретичні відомості

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

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

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

розділений контроль знакової і цифрової чистин зображень результату;

загальний контроль всього зображення.

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

При загальному способі контролю потребує корекцію контрольного коду результату із-за того, що знак результату при додаванні повторює знак доданків.

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

r_A=A - {A/p} p,

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

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

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

А r_A (mod p); B r_B (mod p)

де 0 r_A p-1, то А + В r_A + r_B(mod p).

Звідси

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

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

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

r_{A В} r_A r_B(modp).

3.2 Приклад реалізації методики контролю

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

А = 47 та ?В =-16, якщо модуль p = 3.

Контрольні коди чисел:

r_A= 47 mod 3 = 2, r_B = 16 mod 3 = 1

?Контрольні коди для суми:

A - B = 47-16 = 31, (А+ В) mod 3=(31) mod 9= 0;

r_A+r_B =2+1 = 3, (r_A-r_B)mod 3= (3) mod 3= 0;

Так як (А - В) mod 3 = (r_A+r_B)mod 3=0, то це означає, що операцію віднімання виконано вірно.

Тепер внесемо помилку. Нехай А - В=30, (А - В) mod 3= (30) mod 3=1;

(r_A-r_B)mod 3= (3) mod 3= 0;

Оскільки, (А - В) mod 3(r_A-r_B)mod 3, то існує помилка - операцію додавання виконано невірно.

Таким чином, числовий контроль дозволяє визначити, чи вірний результат було отримано

Висновок

цифровий автомат множення мілі

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

Размещено на Allbest.ru