ЗМІСТ

ВСТУП 

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

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

Виконання курсової роботи базується на знанні студентом таких дисциплін як «Вступ до фаху», «Організація функціонування ЕОМ» та «Комп’ютерна логіка».

Тема курсової роботи  –  синтез операційного та керуючого автоматів.

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

Пояснювальна записка має приблизний обсяг 25÷30 сторінок, синтезована схема оформлюється в додатку на аркуші формату А4 (А3). При оформленні пояснювальної записки необхідно дотримуватися вимог ДСТУ 3008-95.

1. Основні вимоги до змісту розділів пояснювальної записки 

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

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

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

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

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

1.1. Особливості виконання основних арифметичних операцій в електронних обчислювальних машинах (ЕОМ) 

1.1.1. Операція алгебраїчного додавання

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

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

Знакова частина додатного числа містить цифри 00, а від’ємного 11. Ознакою переповнення розрядної сітки є наявність у знаковій частині цифр 01 або 10.

Додавання у прямому коді виконується тільки над числами одного знака. Числа з різними знаками підсумовують в оберненому або доповняльному коді.

Машинна операція додавання чисел з плаваючою комою здійснюється в шість етапів:

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

• виконується  перетворення мантис доданків в один з модифікованих  кодів (обернений чи доповняльний);

• додаються мантиси доданків;

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

• виконується нормалізація суми;

• виконується коригування порядку результату.

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

Кожний зсув мантиси вліво при нормалізації веде до зменшення порядку результату додавання на одиницю. А кожний зсув мантиси вправо – до збільшення. Таким чином відбувається коригування порядку. 

1.1.2 Операція множення

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

Таблиця 1.1 - Правила визначення знака добутку 

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

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

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

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

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

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

1. Дії, що виконуються під час множення обернених (доповняльних) кодів, залежать від знака множника.

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

3. Якщо множник є від'ємним числом, то обернений (доповняльний) код добутку одержується додаванням поправок  і  () до добутку обернених (доповняльних) кодів співмножників.

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

Для чисел  і , що подані в формі з плаваючою комою, добуток обчислюється за формулою 1:

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

- множення мантис;

- додавання порядків;

- нормалізація й округлення мантиси добутку;

- коригування порядку добутку.

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

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

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

1.1.3 Операція ділення

Ділення чисел у двійковій системі числення  класифікується таким чином:

• за формою подання чисел:

- з фіксованою комою;

- з плаваючою комою.

• за механізмом виконання операції:

- з відновленням остачі;

- без відновлення остачі;

• за швидкодією:

- просте;

- прискорене;

• за точністю результату:

- з округленням результату;

- без округлення результату.

 Для того, щоб поділити двійкові числа з відновленням остачі, необхідно виконати такі операції.

1. Подвоїти модуль діленого.

2. Відняти від подвоєного модуля діленого модуль дільника. Одержана різниця  є першою остачею.

3. Проаналізувати знак остачі R. Якщо , то черговому розряду частки присвоїти «1» і перейти до п. 5; якщо ж R < 0, то черговому розряду частки присвоїти «0».

4. Відновити остачу, додавши модуль дільника .

5. Подвоїти остачу.

6. Визначити чергову остачу, віднявши від попередньої остачі модуль дільника. Перейти до п. 3.

Вищевказані дії слід виконувати до одержання всіх необхідних цифр частки.

Алгоритм ділення модулів чисел без відновлення остачi зводиться до виконання таких дій.

1. Подвоїти модуль діленого .

2. Відняти від подвоєного модуля діленого модуль дільника. Одержана різниця  є першою остачею.

3. Проаналізувати знак остачі R. Якщо , то черговому розряду частки присвоїти 1; якщо ж R < 0, то черговому розряду частки присвоїти «0».

4. Подвоїти остачу.

5. Визначити чергову остачу, віднявши від попередньої остачі модуль дільника якщо  і додавши до попередньої остачі модуль дільника якщо R < 0. Перейти до п. 3.

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

Для прискорення операції ділення використовують аналіз старших інформаційних розрядів. Якщо два старші інформаційні розряди дорівнюють одиниці, то у наступний розряд частки записуємо «1», якщо «0», то записуємо «0» і проводимо зсув суматора і регістра результату на два розряди вліво. 

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

Після закінчення операції ділення двійкових чисел за вибраним алгоритмом (з відновленням чи без відновлення остачі, з прискоренням чи без прискорення) для забезпечення округлення результату операцію ділення за вибраним алгоритмом продовжують для визначення ще одного розряду результату. Потім аналізують молодший інформаційний розряд результату. Якщо у цьому розряді записана «1», то її додають до попереднього розряду результату, якщо «0», то останній інформаційний розряд результату просто ігнорують. При використанні методу ділення двійкових чисел без округлення результату описані дії не проводять, обмежуючись виконанням алгоритму ділення.

При діленні двійкових чисел з плаваючою комою спочатку визначають знак результату за правилом алгебри логіки “сума за модулем два”, потім  проводять коригування форми запису чисел (|mA| < |mB|) та визначають порядок результату за формулою 2:

де  - порядок результату;

- порядок числа А;

- порядок числа В.

Далі виконують операцію ділення мантиси числа А на мантису числа В за правилами ділення двійкових чисел з фіксованою комою за одним  з вибраних алгоритмів (з відновленням чи без відновлення остачі; з округленням чи без округлення; просте чи прискорене). Отриманий результат нормалізують. 

1.2 Поняття граф-схеми алгоритму та правила її складання 

Граф-схема алгоритму (ГСА) є найбільш наочною формою подання роботи автомата. ГСА – це орієнтований зв’язний граф, що містить вершини чотирьох типів (рис. 1.1). Кожен з існуючих входів і виходів вершин може розгалужуватись потрібну кількість разів.

а) початкова вершина; б) кінцева вершина:

в) умовна вершина; г) операційна вершина. 

Рисунок 1.1 – Типи вершин ГСА 

Вершина «Початок» входів не має. Вершина «Початок» (рис. 1.1, а) і будь-яка операторна (рис. 1.1, г) вершина мають по одному виходу. Вершина «Кінець» (рис. 1.1, б) виходів не має. Будь-яка умовна вершина (рис. 1.1, в) має два виходи, які позначаються символами «Так» і «Ні». Замість цих символів можуть бути використані цифри «1» і «0», відповідно.

ГСА повинна задовольняти такі вимоги:

1) містити скінченне число вершин;

2) мати лише одну початкову та одну кінцеву вершини;

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

4) кожний вихід повинен з’єднуватись тільки з одним входом;

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

6) для будь-якої вершини графа існує хоча б один шлях до кінцевої вершини;

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

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

1.3 Основні поняття теорії цифрових автоматів 

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

Цифровим автоматом (ЦА) називають пристрій, призначений для обробки та перетворення цифрової інформації. Найбільш розповсюдженим типом цифрових автоматів є комп’ютери.

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

Рисунок 1.2 – Цифровий автомат 

Відповідно до рис. 1.2, математичною моделлю ЦА є деякий абстрактний автомат, який задається таким чином, в початковий момент часу t = t₀, внутрішній стан автомата а(t₀) = a₁ і зберігається таким до моменту часу t = t₁, коли змінюється на стан а₂, ця зміна відбувається під впливом вхідного сигналу Х(t₁). При цьому формується вихідний сигнал Y(t₁)=Y₁, який визначається як функція від внутрішнього стану a₁ і вхідного сигналу х₁: Y=λ(a₁, х₁). В загальному випадку вважається, що при поданні довільного сигналу х_і автомат переходить від стану а(t) в стан а(t+1), який, в свою чергу, є функцією від попереднього стану і вихідного сигналу. В результаті цього переходу виробляється відповідний сигнал Y.

Абстрактний ЦА описується шістьма основними параметрами:

- а₁ – початковий стан автомата;

- А = {} - множина (алфавіт) внутрішніх станів;

- Х = {} - алфавіт вхідних сигналів;

- Y = {} – алфавіт вихідних сигналів;

- δ = {} – сукупність функцій переходу автомата з одного стану в інший;

- λ = {} – сукупність функцій виходу автомата.

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

На відміну від абстрактного автомата, реально використовуються скінченні автомати, які мають скінченні множини вхідних сигналів, вихідних сигналів та внутрішніх станів. Усі скінченні автомати поділяються на повністю визначені, у яких область визначення D функцій δ та λ збігається з множиною перетину алфавітів вхідного та станів, яка є в свою чергу множиною пар ; та неповністю визначені часткові скінченні автомати, для яких функції внутрішніх станів і вихідних сигналів δ та λ визначаються не для всіх пар , Крім того скінченні автомати підрозділяють за виглядом функцій виходів  та переходів . За цією ознакою автомати поділяються на автомати Мілі та Мура. Будь-який автомат можна описати функцією стану і вихідною функцією:

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

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

Процес синтезу керуючого автомата включає такі етапи.

1. Кодоване подання графа мікропрограми або отримання граф-схеми алгоритму роботи керуючого автомата.

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

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

4. Отримання функцій збудження елементів пам’яті (тригерів).

5. Побудова комбінаційної частини автомата.

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

Для автомата Мура вихідний сигнал залежить лише від внутрішнього стану, тобто y=λ(a). Тому кожна операторна вершина повинна бути відмічена символом вихідного стану автомата а_і.

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

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

Таблиця переходів і виходів має однаковий вигляд для автоматів Мілі та Мура і будується в такій послідовності. В полі а_i графи t таблиці 1.2 записуємо поточний стан автомата, в полі а_і графи t+1– наступний його стан, у полі Х – умову переходу зі стану а_i(t) в стан а_i(t+1) згідно із граф‑схемою алгоритму. В полі Y записуються мікрооперації, які виконуються при переході автомата в наступний стан. У полі «Тригери» вказано сигнали, які необхідно подати на входи відповідних запам’ятовувальних елементів. Таким чином описуються всі можливі переходи автомата (табл. 1.2). 

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

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

R = ] log₂ M [ ,                                    (5) 

де М – кількість станів автомата,

R – шукана кількість тригерів.

За отриманою таким чином таблицею записуються та зводяться до мінімальної форми функції збудження тригерів та функції виходів цифрового автомата. Слід пам’ятати, що функції виходів цифрового автомата Мура залежать лише від внутрішніх станів (графа a_i поля t+1) і не залежать від умов переходу Х_і. Далі вибирається система елементів, з яких будується схема автомата. У більшості схем як елементи пам’яті використовуються елементарні автомати (тригери), що мають такі особливості:

1) вони є автоматами Мура і мають два стійких стани;

2) станам елементарного автомата відповідають два різних вихідних сигнали: одиничний (коли на прямому виході тригера одиниця, а на інверсному – нуль) та нульовий;

3) у загальному випадку елементарний автомат може мати декілька фізичний входів.

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

1.5 Контроль виконання арифметичних операцій 

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

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

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

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

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

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

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

При додаванні чисел на суматорі доповняльного коду можливе коригування контрольного коду в випадку, якщо знакові розряди зображень містять одиницю тому, що при цьому виникає одиниця переносу із знакового розряду. Очевидно, що контрольний код суми буде рівним , де – кореляція (=1, якщо виник перенос із знакового розряду, і =0 – якщо переносу немає).

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

Існують два методи отримання контрольного коду: числовий і цифровий.

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

де  – модуль числа,

{А/р} – ціла частина від ділення числа,

 А – контрольне число.

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

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

Цифровий метод контролю. При цифровому методі контролю контрольний код числа утворюється діленням суми цифр числа на вибраний модуль:

де  – модуль числа,

– -та цифра числа.

Можливі два шляхи отримання контрольного коду:

1) безпосереднє ділення суми цифр на модуль р;

2) підсумовування цифр за модулем р.

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

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

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

Якщо відстань між двома числами А₁ та А₂ рівна d, то це означає, що перехід від одного числа до другого досягається додаванням величини d. У цьому випадку всі комбінації чисел, що знаходяться між А₁ та А₂, є забороненими. Відповідно для виявлення d-кратної помилки необхідно мати відстань не меншу за d+1. Якщо d=1, то такий код не зможе виявляти помилки. Величина відстані для кодів AN-вигляду залежить від величин А та N.

Для будь-якого числа А в системі основи q=2 існує єдине подання вигляду де а_і=±1 або 0, в якому немає двох сусідніх коефіцієнтів, відмінних від нуля.

Таке подання містить мінімальне число ненульових коефіцієнтів і називається канонічним. У канонічному поданні вага будь-якого числа, починаючи з 2^і+1 й до числа 2^і+2^і-1, на одиницю більша за вагу чисел від 1 до 2^і-1. Вага чисел, починаючи з 2^і+2^і-1+1 і до 2^і+1, збігається з вагою чисел 2^і+2^і-1-1, 2^і+2^і-1-2 і т. д.

Кількість розрядів для подання числа AN дорівнює log₂(AN)=log₂A+log₂N, де log₂N – надлишковість коду. Таким чином, вибір модуля визначає не тільки надлишковість, але й відстань. Як модуль доцільно вибирати деяке взаємно просте з основою системи q число, що перевищує саму основу.

Можна припустити, що для двійкової системи N=3, і тоді будь-який код вигляду А·3 буде виявляти всі поодинокі помилки. Відповідно мінімальна надлишковість при довільній основі визначається як log_q(q+1), тобто завжди потрібно буде не менше одного, але й не більше двох додаткових розрядів.

Коди з мінімальною відстанню більшою за 2, характеризуються величиною M_q(N, d). Величина M_q(N, d) – найменше число, яке при множенні його на N дає число, вага якого менша за d у поданні за основою q. Іншими словами, якщо число N мало вагу d у поданні за основою q, то добуток N·M_q(N, d) матиме вагу, меншу від d за цією самою основою q.

Якщо число А змінюється в межах 0 ≤А ≤ M_q(N, d) , то при будь-яких N і q мінімальна відстань А·N-коду буде дорівнювати щонайменше d, що випливає з певної кількості M_q(N, d).

В теорії кодування доведено, що M₂(N, 3)=(2^(N-1)/2+1)/N.

Основний спосіб для розрахунку значення М_q – спосіб безпосередніх обчислень (див. [1], С. 163). 

1.6 Завдання на курсову роботу 

У таблицю 1.3 введено такі умовні позначення та скорочення:

Ф.К. – фіксована кома;

П.К. – плаваюча кома;

КА – керуючий автомат;

р – модуль числа. 

Таблиця 1.3 – Варіанти завдань на курсову роботу 

 Продовження таблиці 1.3

Продовження таблиці 1.3

Продовження таблиці 1.3 

 Продовження таблиці 1.3 

1.7 Приклад виконання завдання 

Завдання: синтезувати операційний та керуючий автомати для виконання операції множення на суматорі оберненого коду, починаючи зі старших розрядів множника, з пропуском тактів додавання. Числа подані у формі з плаваючою комою. Тип керуючого автомата – Мура, розрядність операндів 64. Цифровий метод контролю за модулем 5. Контрольні числа :  А = 1118, В = -31. Тип елементів пам’яті – RS-тригер. 

Сформулюємо словесний алгоритм та набір необхідних для розробки пристроїв елементів 

Необхідно

1. Два 56-тирозрядних регістри для зберігання мантис операндів.

2. Два 8-мирозрядних регістри для зберігання порядків операндів.

3. Суматор для додавання мантис операндів.

4. Суматор для додавання порядків операндів.

5. Схема формування оберненого коду.

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

7. Схема порівняння. 

Алгоритм

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

2. Заносимо значення мантиси і порядку числа А в регістри РгАм та РгАп, відповідно.

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

4. Заносимо значення мантиси і порядку числа В у регістри РгВм та РгВп, відповідно.

5. Заносимо в СМм та СМп значення 0.

6. Якщо регістр РгАм= 0, то переходимо в пункт  15.

7. Якщо регістр РгВм = 0, то переходимо в пункт  15.

8. Присвоюємо суматору порядків значення суми регістрів порядків РгАп та РгВп. Заносимо в лічильник значення 55.

9. Якщо множник РгВ від’ємний, то додаємо поправку НСМ := НСМ + [РгАм]об і робимо зсув на один розряд вліво суматора СМм.

10. Аналізуємо старший розряд РгВм[1], якщо він дорівнює 1, то до суматора СМм додаємо РгАм.

11. Виконуємо зсув на один розряд вліво регістра РгВм та суматора СМм, зменшуємо значення лічильника на 1.

12. Аналізуємо вміст лічильника, якщо він дорівнює 0, то переходимо в пункт 13, інакше переходимо в пункт 10.

13. Виконуємо зсув на один розряд вправо суматора СМм.

14. Якщо множник РгВ від’ємний, то додаємо поправку НСМ:=НСМ+РгАм і робимо зсув на один розряд вправо суматора РгАм.

15. Видаємо результат СМм та СМп на шину даних.

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

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

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

Швх – для вхідних даних (множене і множник), які надходять в пристрій через шину вхідних даних;

Швих – для результату (добуток), який видається з пристрою через шину вихідних даних;

РгАм, РгВм – регістри для зберігання мантис операндів;

РгАп, РгВп – регістри для зберігання порядків операндів;

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

СМп – накопичувальний суматор для зберігання порядку результату;

СхФОК – схема формування оберненого коду для формування поправки (не)РгА;

ЛІЧ – лічильник для підрахування кількості кроків (ітерацій) множення. 

Розробимо граф-схему наведеного алгоритму

Блок-схема алгоритму - орієнтований зв'язаний граф, в якому є одна початкова вершина, довільна кількість умовних та операційних вершин і одна кінцева вершина. Така блок-схема подана на рисунку 1.3.

Побудуємо структурну схему операційного автомата

Операційний автомат (ОА) служить для зберігання слів інформації, виконання набору мікрооперацій і обчислення значень логічних умов, тобто операційний автомат є структурою, організованою для виконання дій над інформацією. Мікрооперації, реалізовані операційним автоматом, ініціюються множиною керуючих сигналів Y = {y_{1,  ...,} y_M}, з кожним з яких ототожнюється певна мікрооперація. Значення логічних умов, що обчислюють в операційному автоматі, відображаються множиною інформаційних сигналів X = {x_{1,  ...,} x_L}, кожний з яких ототожнюється з певною логічною умовою. Для цього визначимо набір вхідних і вихідних сигналів (таблиця 1.4).

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

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

Виконаємо множення за розробленим алгоритмом для чисел A = 1118₁₀ та В = -31₁₀.

Запишемо машинне зображення мантис та порядків операндів в оберненому коді, відводячи один розряд на знак і 63 на модуль числа:

 = 0₁0...010001011110₅₅;  = 1₁1...100000₅₅;

= 0₁0...01011₅₅; = 0₁0...0101₅₅; 

Рисунок 1.3 - Граф-схема алгоритму

Таблиця 1.4 - Набір вхідних і вихідних сигналів для структурної схеми операційного автомата 

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

Виконаємо множення мантис (вміст регістрів і операції наведені в таблиці 1.5). 

Таблиця 1.5 – Приклад виконання множення мантис 

СМп=11+5=16.

Отже, у результаті виконання операції на вихідну шину даних потраплять такі дані:

СМм=1₀..1₄₇0111100010011101;

СМп=10000.

Якщо ці дані інтерпретувати у десяткову систему числення, то ми отримаємо число -34658.

-31·1118=-34658.

Отже, ми отримали правильний результат, що підтверджує правильність розробленого алгоритму. 

Закодуємо граф-схему алгоритму виконання операції.

Кодовану граф-схему алгоритму множення наведено на рисунку 1.5.  

Рисунок 1.5 - Кодована граф-схема алгоритму

Побудуємо таблицю переходів та виходів автомата.

Таблиця переходів і виходів будується в такій послідовності.

В полі а_i графи t таблиці записуємо поточний стан автомата, в полі а_і графи t+1– наступний його стан, у полі Х – умову переходу зі стану а_i(t) в стан а_i(t+1) згідно з граф-схемою алгоритму. В полі Y записуються мікрооперації, які виконуються при переході автомата в наступний стан. У полі “Тригери” вказано сигнали, які необхідно подати на входи відповідних запам’ятовувальних елементів. Таким чином описуються всі можливі переходи автомата (таблиця 1.6). 

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

Продовження таблиці 1.6

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

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

Отже, для кодування станів автомата необхідно 5 RS-тригерів: RS0, RS1, RS2, RS3, RS4. Проаналізувавши таблицю 1.6, запишемо функції збудження тригерів:

Також запишемо функції виходів цифрового автомата, враховуючи тип автомата (Мура):

Побудова керуючого автомата

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

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

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

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

Виконання цифрового методу контролю за модулем 5

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

 Рисунок 1.6 – Схема керуючого автомата

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

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

де р – модуль, за яким виконується контроль, у даному випадку він дорівнює 5.

Виконаємо цифровий  контроль виконання операції множення за модулем р = 7 для заданих чисел (А = 1118, В= - 31, C= - 34658): 

Оскільки, множення виконано правильно.

З повагою ІЦ "KURSOVIKS"!