Визначити добуток залишків по модулю п'ять: 0·1, 3·3, 4·3, 2·3, 4·1.

У відповідності з таблицею 2.3 визначимо:

М = 2·3·5 = 30.

Приклад 2.2.1

де с = (с1, с2, с3) = (1, 00, 001);

с1= (0 + 1) = 1 (mod 2);

с2 = (01 + 10) = 00 (mod 3);

с3 = (000 + 001) = 001 (mod 5).

Де с = (с1, с2, с3) = (1, 10, 100);

с1 = (0 - 1) = 1 (mod 2);

с2 = (01 - 10) = 10 (mod 3);

с3 = (000 - 001) = 100 (mod 5).

Приклад 2.2.3

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

1) Незалежність залишків дає можливість побудови ЕОМ у вигляді набору (по числу залишків СЗК) інформаційно незалежних трактів, що працюють паралельно у часі при такій побудові ЕОМ обчислювана система в СЗК має модульність конструкції, що дозволяє здійснювати ремонт і технічне обслуговування не перериваючи розв'язування задач, і для здійснення профілактичних заходів ЕОМ не потрібен висококваліфікований обслуговуючий персонал. Окрім цього помилки, що виникли у тракті m_i, не “розмножуються” в інші тракти ЕОМ, при цьому байдуже чи мала місце на цій підставі однократна чи багаторазова, чи навіть пачка помилок довжиною більш m_i-1 двійкових розрядів. Таким чином, помилка, що виникла в довільному тракті m_i ЕОМ у СЗК або збережеться в цьому тракті до кінця обчислень або у процесі подальших обчислень самоусунеться (наприклад, якщо після виникнення збою в залишку а_і проміжний результат стане числом, що має нульову цифру в залишку по m_i). У цьому випадку за допомогою СЗК можна побудувати систему виправлення помилок при введенні мінімальної надлишковості, що використовує динаміку обчислювального процесу, увівши поняття альтернативної сукупності.

Основна ідея визначення помилкового залишку а_і = а_і+?а_і полягає в тому, що для одержаної в результаті операції послідовності неправильних операндів А_і (і = 1, 2, 3,..., ) у динаміці обчислювального процесу, не перериваючи розв'язання задачі, послідовно визначаються умовні альтернативні сукупності W(А) = W_і-1(А) W_і(А). За визначений час умовна альтернативна сукупність стягається до помилкового залишку (або двох залишків m_i і m_n). Після цього відомими методами проводиться корекція спотвореного залишку а_і. Відмінною рисою даного методу корекції помилок є можливість виправляти помилки без зупинки обчислень, що можливо для ЕОМ, які функціонують в реальному часі.

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

2) Рівноправність залишків. Будь-який залишок а_і числа А_к у СЗК несе інформацію про все вихідне число, що дає можливість чисто програмними методами замінити спотворений тракт по модулю m_i на справний (контрольний) тракт по модулю m_i (m_i < m_i), не перериваючи розв'язання задачі. Окрім того, ЕОМ в СЗК з двома контрольними основами зберігає свою працездатність при відмові будь-яких двох обчислювальних трактів. При виникненні третьої чи навіть четвертої відмови, ЕОМ все ще може виконувати програму при деякому зменшенні точності чи швидкості обчислень, тобто ЕОМ в СЗК є винятково “живучою”, наближаючись в цьому плані до живих організмів. Відзначимо, що дана особливість обумовлює одну із самих чудових властивостей СЗК: та сама ЕОМ може мати різну надійність при розв'язанні задач в залежності від вимог, які висуваються до точності, обсягу пам'яті і швидкодії машини при їх розв'язанні, тобто в процесі розв'язання різних задач на ЕОМ у СЗК можливе здійснення “обмінних” операцій між точністю, швидкодією і надійністю.

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

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

Таблиця 3.2

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

Нехай для заданої операції модульного складання у полі складена таблиця Келі (табл.3.1). З існування нейтрального елементу в полі витікає, що в табл.3.1 є рядок, в якому елементи даного поля стоять в порядку зростання, а з того факту, що в полі залишків ці елементи різні (порядок групи рівний ), витікає, що в кожному рядку (стовпці) табл.3.1 містяться всі елементи поля рівно по одному разу. Використання перерахованих властивостей вмісту таблиці Келі дозволяє реалізувати операції модульного складання і віднімання в СЗК шляхом вживання ПКЗ за допомогою кільцевих - розрядних КЗР.

Нехай довільна система алгебри представлена у вигляді

,

де G- непорожня множина;

- тип операції, визначеної для будь-яких двох елементів.

Операція * + складання в безлічі класів залишків R, породжених ідеалом J, утворює нове кільце, яке називається кільцем класів залишків R/J. Його можна відрекомендувати у вигляді z/(), де z - безліч цілих чисел 0 ±1 +2...; - основа СЗК. (Якщо основа СЗК - просте число, то z/(), - поле). Дана обставина, як зазначалось, і обумовлює можливість реалізації арифметичної операції складання в СЗК без міжрозрядних перенесень шляхом кільцевого зсуву за допомогою вживання групи КЗР.

На основі сформульованого в [32-35] ПКЗ розроблений метод реалізації арифметичних операцій в класі залишків (системі залишкових класів) - метод двійкового кодування. Суть методу полягає в тому, що вихідна цифрова структура для кожного з модулів (основ) СЗК представляється у вигляді вмісту першого рядка (стовпця) таблиці модульного складання (віднімання) виду

, (3.1)

де- операція конкатенації;

- розрядний двійковий код, відповідний значенню -го залишку числа по модулю

Для заданого модуля цифрова структура буде мати такий вигляд

.

Таким чином, за допомогою кільцевих регістрів зсуву, що широко використовуються в ПСЧ, легко реалізувати арифметичні операції в СЗК, причому, виходячи з виразу (3.1), ступені циклічних перестановок визначаються наступними виразами:

(3.2)

(3.3)

Позначимо, що , тобто при z = усі елементи впорядкованої множини залишаються на вихідному місці. При технічній реалізації даного методу перший операнд вказує на номер розряду КРЗ, визначаючого результат модульної операції по модулю , а другий операнд визначає кількість розрядів КРЗ (- двійкових розрядів), на які необхідно провести зсув вихідного (2.4) вмісту КРЗ відповідно до алгоритмів (3.2) (3.3). Хай . Тоді таблиця значень модульної суми для кільця класу залишків z/(5) представиться у вигляді матриці (табл.3.2). Вміст розрядів КЗР представиться у вигляді числових даних, наприклад, першого рядка (стовпця) табл.3.2 (рис.3.1,а). На рисунку знаком позначений позитивний (проти годинникової стрілки) напрям зсуву вмісту розрядів КЗР. При цьому перший операнд вказує номер розряду КЗР, вміст якого визначає результат даної операції, а другий операнд вказує число зсувів вмісту розрядів КЗР (рис.3.1, а, б, в).

Введемо поняття оператора кільцевого зсуву (ОКЗ). ОКЗ - це оператор, що визначає величину (виражену в кількості зсуваємих розрядів КЗР) і напрям зсуву розрядів КЗР, і позначається

Так, для операції модульного складання ОКЗ представиться у вигляді , при цьому час зсуву (утворює в основному час виконання операції) вмісту розрядів КЗР визначається виразом

(3.4)

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

На підставі ПКЗ, використовуючи наступну тотожність

(, (3.5)

можна реалізувати операцію модульного віднімання . У цьому випадку ОКЗ має вигляд .

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

Рисунок 3.1 Варіанти структури кільцевого регістру зсуву для

а) 1-й варіант; б) 2-й варіант; в) 3-й варіант

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

Пристрій містить перший інформаційний вхід 1, перший вхідний регістр 2, дешифратор 3, групу ключових елементів 4, групу елементів І 5, перший елемент АБО 6, вихідний регістр 7, вихід 8 пристрою, другий інформаційний вхід 9, другий вхідний регістр 10, суматор 11 по модулю Р, вхід 12 передачі модуля Р, перший 13 і другий 14 елементи І, другий елемент АБО 15, приймаючий регістр 16, схему 17 порівняння, лічильник 18, шину 19 управління складанням, шину 20 управління відніманням, шину 21 запуску пристрою, генератор 22 імпульсів, третій і четвертий елементи І 23 і 24, помножувач 25 частоти і кільцевий регістр 26 зсуву.

Суматор 11 по модулю Р інвертує другий вхідний операнд В по модулю Р, тобто на виході суматора 11 формується Р-В. Помножувач 25 частоти в раз збільшує кількість вихідних імпульсів генератора 22, де Р - модуль основи СЗК, Р- кількість двійкових розрядів одного розряду регістра 26.

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

Розглянемо роботу пристрою. Для операції модульного складання позначається закономірність розподілу в полі матриці (таблиця, Р = 5) зокрема по рядках, результатів операції. Ця закономірність дозволяє замінити матричний пристрій (ПЗП) кільцевим регістром 26 зрушення, в якому записаний один з рядків таблиці.

Хай необхідно визначити (А + В) mod Р (присутній сигнал на шині 19). Вихідне становище пристрою: нульовий стан всіх регістрів 2, 10, 16 і лічильника 18, в регістр 26 записаний перший рядок таблиці модульного складання.

По входу 1 в двійковому коді поступає перший операнд А в регістр 2, а по входу 9 в двійковому коді - другий операнд В на вхід регістра 10 і на перший вхід суматора 11, на виході якого отримаємо значення Р - В. Сигнал по шині 19 відкриває елемент І 13, через який з виходу регістра 10 через елемент АБО 15 операнд В поступає в приймаючий регістр 16. Дешифратор 3 перетворює операнд А з двійкового коду в десятковий, і на один з ключових елементів 4 поступає сигнал, відповідний значенню А. По сигналу по шині 21 з виходу генератора 22 на входи відкритих елементів И 23 і 24 поступають імпульси. З виходу елементу І 23 через помножувач 25 на вхід регістра 26 поступає послідовність імпульсів, збільшена в n раз. У момент порозрядного збігу стана лічильника 18 і регістра 16 (в обох буде записано значення операнда B) схема 17 порівняння видає сигнал, котрий закриває елементи І 23 і 24 і відкриває відповідний ключовий елемент 4 і елемент І 5, через який значення відповідного розряду регістра 26 поступає на елемент АБО 6 і далі в регістр 7.

Нехай необхідно визначити результат операції (А - В) mod Р (присутній сигнал на шині 20). В цьому випадку з виходу суматора 11 значення (Р - В) через відкритий елемент І 14, елемент АБО 15 поступає в регістр 16. Подальша робота пристрою аналогічна визначенню результату операції модульного складання при вхідних операндах А і Р - В.

Розглянемо приклади конкретного виконання операції модульного складання і віднімання для Р = 5 (n = 3).

Вихідне положення вмісту регістра 26 відповідає значенню першого рядка таблиці, тобто перший розряд - 000, другий - 001, третій - 010, четвертий 011 і п'ятий 100. Схематично вихідний вміст регістра 26 можна представити у вигляді (рис.3.1,б).

Приклад 1. А = 0, В = 2. Необхідно визначити (А + В) mod Р (табл.3.2; рис.3.1,а) Перший операнд А = 000 поступає у вхідний регістр 2, з виходу якого через дешифратор 3 сигнал поступає на вхід першого ключового елементу 4. Другий операнд В = 010 поступає на вхід регістра 10 і на перший вхід суматора 11, на другий вхід якого поступає значення Р = 101. Значення операнда В = 010 через відкритий елемент І 13 (присутній сигнал на шині 19), елемент АБО 15 поступає в регістр 16. Управляючий сигнал по шині 21 запускає генератор 22, імпульси через відкриті елементи І 23,24 поступають відповідно на вхід помножувача 25 і лічильника 18. У момент порозрядного збігу стана лічильника 18 (в лічильники міститься значення 010) і регістра 16 схемою 17 виробляється сигнал,котрий закриває елементи І 23 і 24 і відкриває перший елемент 4, відповідно відкривається перший елемент І 5. Одночасно з виходу помножувача 25 на вхід регістра 26 поступають В*n = =2*3 = 6 імпульсів , котрі зсувають вліво на шість двійкових розрядів (на два розряди регістра 26) первинний вміст регістра, тобто перший вихідний імпульс генератора 22 зсуває вліво вміст регістра 26 на три двійкові розряди. В цьому випадку вміст регістра 26 представляється у вигляді (рис.3.1,в)

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

другий вихідний імпульс генератора 22 зсуває ще вліво вміст регістра 26 на три двійкові розряди. В цьому випадку вміст регістра 26 представляється у вигляді (рис.3.1,в)

Як було показано, після цього вихідний сигнал схеми 17 закриває елементи І 23 і 24, і з виходу генератора 22 імпульси на помножувач 25 не проходять. Після цього вміст першого розряду регістра 26 - 010 (А = 0) через відкритий перший елемент І 5, елемент АБО 6 поступає на вхід регістра 7. Вміст регістра 7 і представлятиме результат операції.

Рисунок 3.2. Пристрій для складання і віднімання по модулю СЗК

Алгоритм підвищення швидкодії виконання операції модульного складання (віднімання) полягає у використанні тотожності (3.2), а також наступних співвідношень:

,

.

У цьому випадку для операції модульного складання ПОКЗ представляється у вигляді

тобто при операнд визначає кількість z зсувів вмісту КЗР, а операнд - номер розряду КЗР, що визначає результат операції; при операнд визначає кількість z зсувів вмісту КЗР, а операнд - номер розряду КЗР, що визначає результат операції.

Для операції модульного віднімання ПОКЗ представляється у вигляді

тобто при операнд визначає кількість z зсувів вмісту розряду КЗР, а операнд - номер розряду КЗР, що визначає результат операції; при операнд визначає кількість зсувів вмісту розряду КСР, а операнд - номер розряду КЗР, що визначає результат операції.

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

Один з алгоритмів підвищення швидкодії виконання операції модульного складання (віднімання) є алгоритм, заснований на властивості наступної тотожності:

(3.5)

тобто зсув вмісту КЗР можна здійснити як в позитивному, так і в негативному напрямах (для , рис.3.1, б), де для операції модульного складання ПОКЗ представляється у вигляді

Надалі для зручності розрахунків, вважатимемо, що - непарне число Для операції модульного віднімання ПОКЗ представиться у вигляді табл. 3.3. Вживання даного алгоритму дозволяє (залежно від величини модуля ) до 90% скоротити значення величини z, що значно зменшує час t виконання модульних операцій (рис.3.3, а, б).

Таблиця 3.3

Рисунок 3.3. Варіанти структури кільцевого регістру зсуву для модуля в СЗК: а) 1-й варіант; б) 2-й варіант; в) 3-й варіант

Розглянемо методи і алгоритми реалізації ПКЗ, що дозволяють удвічі скоротити максимальне значення ПОКЗ (максимальне число зсувів вмісту розрядів КЗР). Очевидно, що . Розглянемо наступний вираз:

. (3.6)

У цьому випадку вміст розрядів КЗР відповідає -й рядку (стовпцю) матриці табл. 3.1 (див. рис. 3.1в), а зсув вмісту розрядів КЗР буде проводитися щодо величини , тобто величина максимальної кількості зсувів вмісту розрядів КСР буде рівна . Таким чином, максимальне значення ПОКЗ рівне

(3.7)

Розглянутий алгоритм (рис.3.3в) виконання операції модульного складання (віднімання) дозволяє істотно підвищити швидкодію виконання модульних операцій в СЗК.

Сучасні ЕОМ при рішенні задач значну частину свого корисного часу витрачають на реалізацію операції множення. ЕОМ приблизно половину часу своєї роботи «присвячує» реалізації операції множення і ділення. Існує достатньо багато методів обійти операцію ділення (наприклад, множення першого операнда на зворотну мультиплікативну величину дільника), проте заміна операції множення сукупністю однотипних операцій складання за допомогою ПКЗ значно знижує призначену для користувача продуктивність ЕОМ. Тому при створенні ЕОМ в СЗК важливо синтезувати пристрій для множення, безпосередньо використовуючи принцип кільцевого зсуву.

Один з варіантів реалізації операції модульного множення ) методом кільцевого зсуву полягає у використанні набору з двох КЗР із застосуванням відомого співвідношення:

(3.8)

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

Розглянемо варіант реалізації операції модульного множення - варіант множини контурів (ВМК). В цьому випадку використовується один КЗР, за допомогою якого визначається і результат модульного складання віднімання, а ОКЗ для операції модульного множення представляється у вигляді , де i - номер контура, в якому проводиться зсув вмісту розрядів КЗР (i =); n - кількість контурів, по яких працює пристрій ; j - номер встановлюваного рядка матриці значень (індекс i для операндів а, опускається);- ПОКЗ, позначаючий кількість зсувів вмісту розрядів КЗР в даному i-м контурі ().

Суть ВМК полягає в тому, що по значенню другого операнда встановлюється ий рядок таблиці значень шляхом зсуву вмісту розрядів КЗР по окремих контурах (по окремих модулях , причому , оскільки мінімальний (перший) модуль рівний двом, тобто , оскільки нульовий рядок таблиці значень не встановлюється (), то Разом з тим перший розряд КЗР встановлюється одночасно з другим і, таким чином, . Нульовий розряд КЗР участі в реалізації ВМК не приймає, оскільки операція множення на нуль простіше організовується по окремому алгоритму, наприклад, шляхом виведення вхідних нульових шин операндів безпосередньо на нульовий вихід пристрою. Встановлення значення вмісту розрядів КЗР проводиться послідовно, починаючи з (-1)-го (старшого) розряду і до другого включно, тобто справа наліво (рис.3.4, 3.5, табл. 3.4).

Таблиця 3.4

Рисунок 3.4 Схема реалізації узагальненої арифметичної операції для довільного модуля СЗК

Рисунок 3.5. Схема реалізації операції модульного множення для

3.3 Виведення аналітичних співвідношень для оцінки ефективності принципу кільцевого зсуву

Введемо поняття узагальненого операнда кільцевого зсуву (УОКЗ) у вигляді матриці , де показник узагальненого операнда кільцевого зсуву (ПУОКЗ) означає кількість зсувів вмісту розрядів КЗР в i-м контурі при встановленні j-го рядка матриці модульного виразу . Таким чином, УОКЗ складатиметься з набору -х ОКЗ і може бути розкладений або по рядках , або по контурах у вигляді

(3.9)

(3.10)

Виходячи із запису УОКЗ (3.10), можна визначити тимчасову матрицю :

(3.11)

Час встановлення j-го рядка матриці (час реалізації операції) значень рівен сумі ПУОКЗ для j-го рядка матриці (3.11), помноженої на величину (3.4)

. (3.12)

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

, (3.13)

а час встановлення j-го рядка матриці рівне сумі ПУОКЗ для j-го стовпця матриці (3.13), помноженої на величину . Очевидно, що в загальному випадку час t реалізації модульної операції , як і для операції модульного складання і віднімання, залежить від величини операнда (від номера j встановлюваного рядка), тобто

. (3.14)

Виходячи з виразу (3.14), доцільно оперувати середнім і максимальним часом реалізації модульних операцій

, (3.15)

. (3.16)

Відповідно до виразу (3.12) запишемо формули (3.15), (3.16) у вигляді

, (3.17)

, (3.18)

а для операції складання (віднімання) формула (3.4) представиться у вигляді

, (3.19)

. (3.20)

Відзначимо, що в кожному з контурів можна застосувати розроблені вище алгоритми скорочення часу встановлення потрібного рядка таблиці даної модульної операції. В цьому випадку результат операції модульного множення визначатиметься за час менший, ніж те, що визначається виразами (3.17) - (3.18). Відомо, що час реалізації операцій складання і множення у ПСЧ визначається наступними виразами:

, (3.21)

. (3.22)

де с - кількість двійкових розрядів в поданні операндів (розрядна сітка ЕОМ); () - час проходження сигналу через елемент І (АБО) (час «спрацювання» відповідного логічного елементу). Беручи до уваги, що , запишемо вирази (3.22) і (3.23) у вигляді

, (3.22)

. (3.23)

Проведемо порівняльний аналіз часу реалізації арифметичних операцій в ПСЧ і в СЗК для однобайтового (l = 1) і чотирьохбайтового (l = 4) машинного слова. Для l = 1 (с=8) СЗК може представлятися набором наступних основ: для l= 4(с=32) -

Відзначимо, що час реалізації арифметичних операцій в СЗК за принципом кільцевого зсуву визначається часом реалізації даної модульної операції для максимального по величині модуля СЗК, тобто для l = 1 - це модуль = а для l= 4 - це модуль =Відповідно до формул (3.17) - (3.22) розрахуємо максимальний і середній час для реалізації арифметичних операцій (табл. 3.5) без вживання алгоритмів їх прискорення в СЗК і для двійкових ПСЧ. З таблиці 3.5 видно, що вживання принципу кільцевого зсуву, навіть без вживання алгоритмів підвищення швидкодії виконання модульних операцій, дозволяє зменшити, в порівнянні з ПСЧ, час реалізації модульної операції арифметичного множення при прийнятному часі виконання модульної операції складання (віднімання) в СЗК. Відзначимо, що із збільшенням величини l ефективність вживання ПКЗ для виконання арифметичної операції множення в класі залишків зростає

Таблиця 3.5 Дані продуктивності СОКІ

Розглянемо приклад конкретної реалізації операції модульного множення при

УОКЗ для представимо у вигляді

, (3.24)

У загальному вигляді УОКЗ розкладемо по рядках і контурах.

По рядках:

,

,

.

По контурах:

,

,

,

На підставі співвідношення (3.24) УОКЗ для відповідно другої третьої (j=3) і четвертої (j=4) рядків табл. 3.4 матиме наступний вигляд:

,

,

.

Загальний алгоритм утворення ПОКЗ для представлений в табл.3.6 (див. рис. 3.5). Визначимо час встановлення j-го рядка табл.3.6 відповідно до виразу (3.4): ф, ф, ф . Визначемо, що відповідно до виразу (3.22) максимальний час встановлення j-й строки Дана обставина підтверджує, що реальна ефективність використання ПКЗ вище, ніж та, що визначається виразами (3.17) та (3.20).

Таблиця 3.6 Алгоритм реалізації операції множення

Основним недоліком останнього розглянутого методу реалізації арифметичних операцій в класі залишків є тривалість їх виконання, що знижує ефективність використання ПКЗ. Цей недолік обумовлений тим, що структура (3.1) представлена набором початкових залишків першого рядка матриці ,що відображається двійковим кодом. В цьому випадку час реалізації модульного складання двох операндів та в СЗК визначається виразом

, (3.25)

Де - час зсуву одного біта інформації (одного двійкового розряду), де для .

З метою усунення вказаного недоліку і підвищення ефективності реалізації арифметичних операцій в класі залишків пропонується новий метод реалізації арифметичних операцій, також заснований на використанні ПКЗ - метод унітарного кодування, суть якого полягає в тому, що інформаційна структура довільного модуля СЗК представляється у вигляді унітарного (m-1) - розрядного коду

(3.26)

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

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

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

. (3.27)

Раніше наголошувалося, що час реалізації арифметичної операції А ± В у класі залишків визначатиметься часом виконання операції для максимального значення залишку з сукупності для даного операнда , тобто

. (3.28)

Аналіз виразів (3.25) і (3.28) показує, що розроблений метод унітарного представлення зменшує час виконання арифметичних операцій в порівнянні з методом двійкового кодування в раз. Для з'ясування алгоритму реалізації арифметичних операцій в класі залишків на підставі розробленого методу розглянемо приклад конкретної реалізації операції складання А + В для СЗК, заданими основами . Нехай А = (0, 10, 100) і В=(1,01,010) (табл. 3.7). Оскільки , то відповідно до виразу (3.28) час реалізації операції складання в СЗК для даних операндів рівно ; і в цьому випадку алгоритм реалізації операції складання повністю визначається алгоритмом реалізації операції модульного складання по найбільшому модулю СЗК. Вихідний вміст КРЗ визначається у вигляді

Таблиця 3.7

Перший операнд дешифрується і значення в унітарному коді заноситься в четвертий розряд КРЗ, вміст якого приймає вигляд

Другий операнд також дешифрується і отримане значення визначає кількість z зсувів в позитивному (проти годинникової стрілки) напрямку вмісту КРЗ. У результаті вміст КРЗ представляється так:

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

Таблиця 3.8 Алгоритм шифрування

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

Проведемо загальну порівняльну оцінку часу реалізації арифметичних операцій в ПСЧ і в класі залишків при використанні ПКЗ. Відомо, що час реалізації арифметичних операцій складання і множення в ПСЧ для l - байтових машинних слів визначається виразами (3.22) і (3.23), де , а можливий максимальний час реалізації відповідних арифметичних операцій для ПКЗ при вживанні методу двійкового подання буде рівний

(3.29)

. (3.30)

Виходячи з виразів (3.6) і (3.7), видно, що максимально можливий час реалізації арифметичних операцій в класі залишків при використанні методу унітарного кодування для операції складання рівно

(3.31)

а для множення

, (3.32)

оскільки , тобто операнд в унітарному коді заноситься в КЗР, а потім послідовно проводиться складання по схемі.

Розрахунки (табл.3.9), проведені відповідно до виразів (3.22), (3.23), (3.29) - (3.32), показали високу ефективність методу унітарного кодування з погляду мінімізації часу реалізації арифметичних операцій в класі залишків в порівнянні з методом двійкового кодування в СЗК і часом реалізації таких же операцій в ПСЧ. Вживання запропонованих алгоритмів дозволить (залежно від величини модуля і значення операнда ) до 90% скоротити максимальний час реалізації арифметичних операцій в СЗК. Модульність структури обчислювального процесу в класі залишків дає можливість ефективно застосувати ПКЗ для реалізації основних арифметичних операцій. Використання ПКЗ дозволить, як і при табличному принципі, усунути вплив міжрозрядних зв'язків між двійковими розрядами операндів А і В на результат обчислень при прийнятній кількості устаткування операційного пристрою ЕОМ.

Таблиця 3.9 Дані продуктивності СОКІ у МСЧ

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

Рисунок 3.6. Схема функціонування операційного пристрою СОКІ у МСЧ для ПКЗ а) 1-й алгоритм; б) 2-й алгоритм

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

Очевидно, що максимальної швидкодії виконання арифметичних операцій при вживанні принципу кільцевого зсуву можна досягти, використовуючи програмний метод реалізації модульних операцій. В цьому випадку, використовуючи керуючі матриці, в більшості варіантів результат операції можна досягти за менше, ніж , число зсувів двійкових розрядів. Це обумовлено тим, що зсув вмісту КЗР проводиться відповідно до даних керуючих матриць на число двійкових розрядів, кратне величині, тобто на мінімально необхідне число двійкових розрядів. Здійсненність даної процедури обумовлена надмірністю вмісту розрядів КЗР. Вміст керуючих матриць визначається для кожної операції (складання, віднімання і т.п.) і для кожної підстави СІК індивідуально. Вузлу керуючої матриці привласнюється значення (з урахуванням напряму зсуву), рівне кількості необхідних зсувів вмісту двійкових розрядів КЗР. Для вміст керуючих матриць операцій складання, віднімання і множення розрахований і представлений відповідно в табл. 3.10-3.11

Таблиця 3.10

Таблиця 3.11

Таблиця 3.12

Результати розрахунків показали, що час реалізації модульних операцій складання (віднімання) і множення в порівнянні з часом реалізації, представленим в табл. 3.9, значно скорочується.

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

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

за рахунок помилкових перенесень при виконанні арифметичних операцій;

у процесі перенесень при виконанні арифметичних операцій.

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

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

Через властивість ПКЗ вага вектора вмісту КЗР завжди постійний, тобто

(3.33)

Співвідношення (3.33) можна представити у вигляді

. (3.34)

Виходячи з властивості ПКЗ, математично визначеним співвідношеннями (3.33), (3.34), очевидно, що технічно за допомогою введення лічильника значень можна знайти всі помилки непарної кратності вигляду ,, а з введенням лічильника значень усувається вплив помилок, що виникли за рахунок збоїв при порушенні синхронізації зсувів вмісту КЗР.

Розглянемо приклад конкретного виконання операції модульного складання в полі для (таб.3.2) з урахуванням корегуючих здібностей коду СЗК при використанні ПКЗ.

На рис.3.7 представлений вихідний вміст КЗР для .

Для даного прикладу ваги відповідних розрядів КЗР такі:

Таким чином,