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

1.3 Розробка машинного алгоритму

1.3.1 Побудова граф-схеми алгоритму Побудова словесного алгоритму:

1) У регістр А записується прямий код множеного А, який передається із вхідної шини:

РгА:=Швх1

2) У регістр В записується прямий код множника В, який передається із вхідної шини:

РгВ:=Швх2

3) Встановлюємо в нуль накопичувальний суматор:

НСМ:=0

4) У лічильник записуємо кількість разів повторення циклу:

ЛІЧ:=29

5) Перевіряємо чи рівні знакові розряди співмножників:

РгА[31]=РгВ[31] ?

Якщо так,то переходимо до пункту 7.

Якщо ні, то переходимо до пункту 6.

6) Знаковий розряд НСМ виставляється в 1:

НСМ[63]:=1

7) Аналізуємо старший розряд регістра В:

РгВ[30]=1?

Якщо так, тоді переходимо до пункту 8.

Якщо ні, тоді переходимо до пункту 9.

8) Додаємо до вмісту накопичувального суматора значення коду регістра А:

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

9) Відновлюємо попередній вміст регістра В, циклічно зсуваючи його вліво на один розряд:

L1.РгB[0:30]

10) Вміст накопичувального суматора циклічно зсуваємо на один розряд вліво:

L1.НСМ[0:62]

11) Декрементуємо значення лічильника:

ЛІЧ:=ЛІЧ-1

12) Молодший розряд накопичувального суматора приймає значення нуль:

НСМ[0]=0

13) Перевіряємо, чи лічильник рівний нулеві:

ЛІЧ=0?

Якщо так, то переходимо до пункту 14

Якщо ні, то переходимо до пункту 7.

14) Значення накопичувального суматора циклічно зсуваємо на один розряд вправо:

R1.НСМ[0:62]

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

Швих:=НСМ[0:63]

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

Граф-схема алгоритма (ГСА) - орієнтований зв'язаний граф, який містить одну початкову вершину (Початок), одну кінцеву вершину (Кінець) і довільну кількість умовних і операторних вершин. Вершина "Початок" входів не має.

Кінцева, операторна і умовна вершини мають по одному входу, початкова вершина входів не має. Вершина "Початок" і будь-яка операторна мають по одному виходу, умовна вершина має два виходи, позначених символами «1» та «0». Вершина "Кінець" виходів не має.

ГСА має задовольняти наступні умови:

входи і виходи вершин з'єднуються один з одним за допомогою дуг, направлених завжди від виходу до входу;

кожен вихід з'єднано лише з одним входом;

кожен вихід з'єднується лише з одним входом;

будь-який вхід з'єднується принаймні з одним виходом;

будь-яка вершина ГСА лежить принаймні на одному шляху від початкової вершини до кінцевої;

один із виходів умовної вершини може з'єднуватись з її входом, що є недопустимим для операторної вершини. Такі умовні вершини іноді називаються зворотними;

в кожній умовній вершині записується логічна умова із множини логічних умов;

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

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

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

Рисунок 1 - Структурна схема операційного автомата

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

Приклад: Перемножити на суматорі прямого коду починаючи з старших розрядів множника А=57, В=-923 з використанням описаного у пункті 1.3.1 алгоритму.

Розв’язання.

Спочатку запишемо машинні зображення чисел А та В в прямих кодах з заданою розрядністю:

А = 0,[0] ₃₀...[0] ₆111001; В = 1,[0] ₃₀…[0] ₁₁1110011011

Послідовність дій, що виконуються над числами, наведена у таблиці 1.

Відповідь: 1,[0] ₆₂…[0] ₁₇01100110011011000.

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

Суматор НСМ	Регістр РгА	Регістр РгВ	Примітки
0,[0]62…[0]1700000000000000000	0,[0]30...[0]6111001	1,[0]30…[0]111110011011	НСМ:=0; РгА:=Швх1; РгВ:=Швх2; ЛІЧ:=29;
1,[0]62…[0]18000000000000000000	0,[0]30...[0]6111001	1,[0]30…[0]121110011011_	НСМ[63]:=1; РгВ[30]=0; L1.РгВ[0:30]; ЛІЧ:=28; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1700000000000000000	0,[0]30...[0]6111001	1,01110011011[ _ ] 19…[ _ ] 0	РгВ[30]=0; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=10;
1,[0]62…[0]1700000000000000000 1,[0]62…[0]1700000000000111001 1,[0]62…[0]1700000000001110010	0,[0]30...[0]6111001	1,1110011011[_] 20…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=9;
1,[0]62…[0]1700000000001110010 1,[0]62…[0]1700000000010101011 1,[0]62…[0]1700000000101010110	0,[0]30...[0]6111001	1,110011011[_] 21…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=8;
1,[0]62…[0]1700000000101010110 1,[0]62…[0]1700000000110001111 1,[0]62…[0]1700000001100011110	0,[0]30...[0]6111001	1,10011011[_] 22…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=7;
1,[0]62…[0]1700000001100011110 1,[0]62…[0]1700000011000111100	0,[0]30...[0]6111001	1,0011011[_] 23…[_] 0	РгВ[30]=0; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=6;
1,[0]62…[0]1700000011000111100 1,[0]62…[0]1700000110001111000	0,[0]30...[0]6111001	1,011011[_] 24…[_] 0	РгВ[30]=0; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=5;
1,[0]62…[0]1700000110001111000 1,[0]62…[0]1700000110010110001 1,[0]62…[0]1700001100101100010	0,[0]30...[0]6111001	1,11011[_] 25…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; ЛІЧ:=4; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1700001100101100010 1,[0]62…[0]1700001100110011011 1,[0]62…[0]1700011001100110110	0,[0]30...[0]6111001	1,1011[_] 26…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; ЛІЧ:=3; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1700011001100110110 1,[0]62…[0]1700110011001101100	0,[0]30...[0]6111001	1,011[_] 27…[_] 0	РгВ[30]=0; L1.РгВ[0:30]; L1.НСМ[0:62]; НСМ[0]:=0; ЛІЧ:=2;
1,[0]62…[0]1700110011001101100 1,[0]62…[0]1700110011010100101 1,[0]62…[0]1701100110011011000	0,[0]30...[0]6111001	1,11[_] 28…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; ЛІЧ:=1; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1701100110011011000 1,[0]62…[0]1701100110110000011 1,[0]62…[0]1711001100110110000	0,[0]30...[0]6111001	1,1[_] 29…[_] 0	РгВ[30]=1; НСМ:=НСМ+РгА; L1.РгВ[0:30]; ЛІЧ:=0; L1.НСМ[0:62]; НСМ[0]:=0;
1,[0]62…[0]1711001100110110000 1,[0]62…[0]1701100110011011000	0,[0]30...[0]6111001	1,1[_] 29…[_] 0	R1.НСМ[0:62]; Швих:=НСМ[0:63]

2. СИНТЕЗ КЕРУЮЧОГО АВТОМАТУ

 

2.1 Основи теорії керуючих автоматів

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

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

Існують два основні типи керуючих автоматів

1. Керуючий автомат з жорсткою чи схемною логікою. Для кожної операції будується набір комбінаційних схем які в потрібних тактах збуджують відповідні керуючі сигнали. Іншими словами будується скінчений автомат в якому необхідна множина станів представляється станами k запам’ятовуючих елементів

q = {q1 q2, …, qk}

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

Послідовність мікрокоманд що виконують одну машинну команду чи окрему процедуру створює мікропрограму. Звичайно мікропрограми зберігаються в спеціальній пам’яті мікропрограм (керуючій пам’яті).

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

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

Скоротити довжину мікрокоманд дозволяє застосування вертикального мікропрограмування при якому кожна мікрооперація кодується ]log2 n[ - розрядним кодом де n – загальна кількість мікрооперацій. Таке кодування накладає обмеження на методи виконання операцій а саме не повинно бути операцій що потребують одночасного виконання ряда мікрооперацій. В тих випадках коли це обмеження виконати неможливо треба використовувати складні мікрооперації що складаються з сукупності простих.

2.2 Опис керуючого автомату Мілі

За способом формування функції виходів виділяють три типи абстрактних автоматів: автомат Мілі, автомат Мура та С-автомат.

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

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

Автомат Мілі характеризується системою рівнянь:

(2.1)

де  – множина вхідних сигналів автомата (вхідний алфавіт);

– множина станів автомата (алфавіт станів);

– множина вихідних сигналів (вихідний алфавіт).

λ – функція виходів автомата;

φ – функція переходів автомата.

Іншими словами, функція виходів λ задає відображення (XS)→Y, тобто ставить у відповідність будь-якій парі елементів декартового добутку множин (XS) елемент множини S.

2.3 Кодування граф-схеми автомату

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

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

  2.4 Побудова таблиці переходів

Умови переходу по мікропрограмі від одного стану до іншого задають функцію переходів автомата.

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

Іноді при завданні автоматів Мілі використовують одну суміщену таблицю переходів і виходів, в якій на перетині стовпця а_m і рядка х_j записуються у вигляді а_s/y_g наступний стан і вихідний сигнал, що видається.

У таблиці 4 для заданого автомата маємо суміщену таблицю переходів і виходів.

Таблиця 2 – Таблиця переходів і виходів

t			t+1			Тригери
						JK2		JK1		JK0
ai	код ai	xi	ai+1	код ai+1	yi	J2	K2	J1	K1	J0	K0
a0	000		a1	001	y1,y2,y3,y4	0	0	0	0	1	0
			a2	010		0	0	1	0	0	0
			a3	011		0	0	1	0	1	0
a1	001		a2	010	y5	0	0	1	0	0	1
			a3	011		0	0	1	0	0	0
a2	010	___	a3	011	y6	0	0	0	0	1	0
a3	011	___	a4	100	y7,y8	1	0	0	1	0	1
a4	100		a5	101	y9,y10	0	0	0	0	1	0
			a2	010		0	1	1	0	0	0
			a3	011		0	1	1	0	1	0
a5	101	____	a6	110	y11	0	0	1	0	0	1
a6	110	____	a0	000	y12	0	1	0	1	0	0

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

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

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

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

вихідний сигнал y(t) однозначно визначається вхідним сигналом x(t) і станом а(t-1) автомата в слідуючий момент часу;

вихідний сигнал y(t) однозначно визначається вхідним сигналом x(t) і станом а в даний момент часу.

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

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

В нашому випадку буде використовуватись три логічні умови Х = {х1,x2,х3} і дванадцять мікрооперацій Y = {y1, …, y10}

Отже, для кодування станів автомата необхідно 3 JK-тригера: JK0, JK1, JK2,. Закодуємо стани автомата так, як це показано у таблиці 5.

Для побудови функцій збудження тригерів і виходів використовується структурна таблиця автомата (таблиця 5).

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

Функції виходів:

;

;

;

;

;

;

;

;

;

;

.

Функції збудження тригерів:

;

;

;

.

3. МЕТОДИКА КОНТРОЛЮ 3.1 Теоретичні відомості

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

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

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

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

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

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

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

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

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

Одним з таких кодів є AN-код, де А-контролюєме число, N-модуль. Для таких кодів змінюються поняття відстані і ваги.

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

А = 2^і – 1 , і=2,3,…

АN₁  АN₂ = A(N₁  N₂)

Якщо ділення виконується без остачі, помилок немає, якщо з остачею – помилки є.

АN₁ АN₂ = A²N₁ N₂

АN – використовуються для контролю лише в тих пристроях, де реалізується операція ділення.

3.2 Приклад контролю виконання операції множення за допомогою 11N-коду

Виконаємо числовий контроль за допомогою 11N-коду для заданих чисел:

N₁ = 57

N₂ = -923

A=11

11*57*(-923)*11 = 121*(-52 611) = -6 365 931

Тепер отримане число ділимо на 121:

-6 365 931/121 = -52611

Отримаємо -52611 – це означає що націло ділиться отже не існує помилки. Остача в цьому прикладі дорівнює нулю.

Внесемо похибку в обчислення:

-6 365 933/121 = -52611 і остачу 2, отже результат не збігається.

ВИСНОВКИ

 

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

ПЕРЕЛІК ПОСИЛАНЬ

 

1.   Методичні вказівки до оформлення курсових проектів (робіт) у Вінницькому національному технічному університеті / Г.Л. Лисенко, А.Г. Буда, Р.Р. Обертюх. – Вінниця: ВНТУ, 2006. – 60 с.

2.   Прикладная теория цифровых автоматов: Учеб. для вузов по спец. ЭВМ / А.Я. Савельев. – М.: Высшая школа, 1987. – 272 с.

3.   Прикладная теория цифровых автоматов / К.Г. Самофалов, А.М. Романкевич, В.Н. Валуйский, Ю.С Каневский, М.М. Пиневич. – К.: Вища школа. Головное изд-во, 1987. – 375 с.

4.   Структура электронных вычислительных машин / С.А. Майоров, Г.И. Новиков. – Л.: Машиностроение. Ленинградское отделение, 1979. – 384 с.

5.   Электронные вычислительные машины и системы: Учеб. пособие для вузов. – 3-е изд., перераб. и доп. / Б.М. Каган. – М.: Энергоатомиздат, 1991. – 592 с.

6.   Цифровые ЭВМ: Теория и проектирование / К.Г. Самофалов, В.И. Корнейчук, В.П. Тарасенко. – К.: Выща школа. Головное изд-во, 1989. – 424 с.

7.   Справочник по цифровой схемотехнике / В.И. Зубчук, В.П. Сигорский, А.Н. Шкуро. – К.: Тэхника, 1990. – 448 с.