9.1 Прямий, обернений, доповняльний  код

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

Натуральним кодом називають подання числа як цілого беззнакового у двійковій системі числення. Діапазон чисел у натуральному коді для n – розрядної сітки становить від 0 до 2n - 1, тобто для 8-розрядної сітки діапазон чисел у натуральному коді - від 0 до 255. Наприклад, натуральний код числа 5310 у 8-розрядній сітці наведено на рис. 9.1

Рисунок 9.1 – Натуральний код числа 5310 у 8-розрядній сітці

Для подання цілих знакових чисел використовують прямий, обернений і доповняльний коди. Старший розряд сітки є знаковим. Значення цього розряду дорівнює 0 для додатних чисел і 1 - для від’ємних. В інших розрядах розміщується модуль числа. Додатні числа подаються однаково у всіх трьох кодах. Так, додатне число  +5310 має вигляд, поданий на рис. 9.1. Але оскільки старший розряд є знаковим, діапазон додатних чисел становить від 0 до 2n-1 - 1. Наприклад, для 8-розрядної сітки діапазон додатних чисел - від 0 до +127. Подання від’ємних чисел залежить від використання того чи іншого коду.

Подання від’ємного числа у прямому коді здійснюється так. У старшому, знаковому, розряді розміщується 1, а в інших розрядах - модуль числа. Діапазон від’ємних чисел у прямому коді становить від 0 до -(2n-1- 1). Для прикладу на рис. 9.2 наведено прямий код числа -5310 у 8-розрядній сітці, для якої діапазон від’ємних чисел - від 0 до -127 = 11111111.

Рисунок 9.2 – Прямий код числа -5310 у 8-розрядній сітці

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

Недоліками прямого коду є те, що операції додавання і віднімання чисел з різними знаками потребують додаткових операцій для визначення більшого за модулем числа та знака результату. Крім того, наявність знака при поданні числа 0 (+0 = 000000   і  -0 = 1000000) потребує виконання зайвих операцій.

Подання від’ємного числа у оберненому коді здійснюється обчисленням числа, яке доповнює додатне число з тим самим модулем до найбільшого беззнакового числа, яке може бути розташоване в даній розрядній сітці. Одержання оберненого коду від’ємного числа зводиться до порозрядного інвертування розрядів додатного числа, включаючи знаковий розряд. Діапазон від’ємних чисел у оберненому коді становить від 0 до -(2n-1-1). Як приклад на рис. 9.3 показано обернений код числа -5310 у 8- розрядній сітці, для якої діапазон від’ємних чисел – від 0 до -12710, при цьому оберненим кодом найменшого числа -12710 є число 100000002.

Рисунок 9.3 – Обернений код числа -5310 у 8-розрядній сітці

Розглянемо віднімання двох чисел в оберненому коді на прикладі чисел +16310 і +5310. Подамо різницю у вигляді:

12510- 5310 = 12510 + (25510 - 5310) – 25510.                (9.1)

Вираз (25510 - 5310) є оберненим кодом від’ємного числа -5310, тобто доповненням до найбільшого числа 25510 = 111111112, що можна розмістити у 8-розрядній сітці. З виразу 9.1 випливає, що операцію віднімання можна замінити операцією додавання в оберненому коді з подальшим коригуванням результату (відніманням 25510). Виконання операції додавання числа 12510 та числа -5310 поданого в оберненому коді, показано на рис. 9.4.

Рисунок 9.4 – Виконання операції додавання числа 12510 та числа -5310, поданого в оберненому коді

Під час додавання виникає перенесення у неіснуючий дев’ятий розряд, тобто переповнення розрядної сітки. Це зменшує отриманий результат на 25610. Оскільки згідно з виразом (9.1) результат треба зменшити на 25510, для правильного результату потрібно до одержаної суми додати одиницю. Після такого коригування відповідь становитиме +7110 + 110 = +7210 = +010010002, що відповідає виразу (9.1). Коригування результату досягається апаратними засобами – реалізацією додавання до молодшого біта значення перенесення, яке виходить за розрядну сітку. У цьому прикладі має місце перенесення одиниці в неіснуючий дев’ятий розряд. Нульове значення знакового розряду результату означає, що різниця чисел додатна.

Перевагами оберненого коду є простота операцій одержання та додавання чисел із різними знаками, недоліками - два подання нуля: +0 = 00000000 і -0 = 111111111, а також потреба в апаратній реалізації коригування результату.

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

Доповняльний код можна одержати за таким формальним правилом: цифри прямого коду додатного числа необхідно інвертувати послідовно зліва направо до останньої одиниці, не включаючи її. Останню праву одиницю і наступні за нею (праворуч) нулі слід залишити без зміни. Діапазон від’ємних чисел у доповняльному коді становить від 0 до -2n-1. Як приклад на рис. 9.5 показано доповняльний код числа -510 у 8-розрядній сітці, для якої діапазон від’ємних чисел - від 0 до -12810, при цьому доповняльним кодом найменшого числа -128 10 є число 100000002.

Рисунок 9.5 – Доповняльний код числа -5310 у 8-розрядній сітці

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

12510 - 5310 = 12510 + (25610 - 5310) - 25610.                 (9.2)

Вираз (25610 - 5310) є доповняльним  кодом від’ємного числа -5310. 3 виразу (9.1) випливає, що операцію віднімання можна замінити операцією додавання у доповняльному коді. Виконання операції додавання числа 12510 та числа -5310, поданого у доповняльному  коді, ілюструє рис. 9.6.

Рисунок 9.6 – Виконання операції додавання числа 12510 та числа -5310, поданого у доповняльному коді

Унаслідок додавання відбулося переповнення, тобто перенесення у неіснуючий дев’ятий розряд, що зменшило результат на 25610. Отже, відповідно до формули (1.4) отримана сума і буде остаточним результатом.

Перевагами доповняльного коду є простота операцій одержання та додавання чисел із різними знаками, а також те, що нуль має єдине подання: 0 = 00000000. Завдяки цим перевагам доповняльний  код використовують найчастіше.

9.2 Модифіковані коди

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

Приклад. Додати два числа А(2) = – 0,10101 і В(2) = – 0,11001 в оберненому і доповняльному  кодах.

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

Модуль суми цих чисел більший за одиницю, тобто |A + В| > 1.

Виконаємо додавання цих чисел

Отриманий результат є невірним з двох позицій.

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

По-друге, в цифрових розрядах числа також отримане невірне значення. Це виходить через те, що результат додавання не вкладається в розрядну сітку комп’ютера, тобто спостерігається переповнення розрядної сітки. Таке явище відбувається кожного разу, коли абсолютне значення суми більше одиниці, тобто при |A + В| > 1.

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

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

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

Приклад. Подати число А(2) = – 0,101011 в прямому, оберненому і доповняльному модифікованих кодах.

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

[А]пМ = 11.101011;   [А]оМ = 11.010100;   [А]дМ = 11.010101.

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

Приклад. Виконати додавання чисел А(2) = – 0,00101 і В(2) = – 0,10011 в оберненому і доповняльному модифікованих кодах. Результат подати в прямому коді.

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

Відповідь: [А + В]п = 1.11000

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

У випадку переповнення розрядної сітки в комп’ютерах з фіксованою комою він зупиняється. Це свідчить про те, що масштабування виконане невірно. Для усунення переповнення розрядної сітки необхідно знову виконати масштабування.

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

Приклад. Додати два числа, записані в формі з плаваючою крапкою з використанням доповняльного модифікованого коду:

А(2) = – 0,110110 ·2011 і В(2) = – 0,001101 ·2011 .

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

Видно, що відбулося переповнення розрядної сітки. Виконуємо зсув мантиси і її знаку на один розряд вправо і збільшення порядку на одиницю:

[А + В]ДМ  = 11.0111101 0.100.

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

9.3 Кодування, захищене від завад

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

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

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

Можливість виявлення помилок за наявності додаткових бітів обумовлена тим, що для передачі інформації використовуються не всі можливі комбінації в кількості N = 2n, а лише деяка частина з них –  N0 < N. Комбінації з безпомилковою інформацією є дозволеними, інші N - N0 комбінацій є забороненими. Поява заборонених комбінацій розглядається як помилка. Можливі такі помилки, за яких одна дозволена комбінація переходить у іншу. У цьому разі помилки не виявляються. Загальна кількість можливих помилок визначається добутком N • N0. З цієї кількості помилок буде виявлено N0(N – N0). Відношення кількості виявлених до загальної кількості можливих помилок називають коефіцієнтом виявлення коду:

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

Ступінь відмінності двох кодових комбінацій характеризується кодовою відстанню d, тобто кількістю бітів, які є різними для двох комбінацій. Кодова відстань може набувати значень від 1 до n, де n - довжина кодової комбінації. Кодову відстань можна визначити, обчисливши суму двох комбінацій за модулем 2 і підрахувавши кількість одиниць у цій сумі. Якщо d - 1, то всі кодові комбінації є дозволеними, а виявлення і виправлення помилок неможливе. При d - 2 одноразові помилки переводять дозволені комбінації в заборонені, тому такий код може виявляти всі одноразові помилки, а також помилки непарної кратності (помилки одночасно у трьох, п’яти, семи і так далі розрядах). Помилки парної кратності (помилки одночасно у двох, чотирьох, шести і так далі розрядах) таким кодом не виявляються. Якщо необхідно виявляти помилки кратності r, то мінімальна кодова відстань dmin між комбінаціями коду має бути хоча б на одиницю більше від кратності помилки  dmin > = r +1.

Коректувальна здатність коду забезпечується введенням k додаткових перевірних бітів. Тоді загальна довжина кодової комбінації буде n + k, а загальна кількість можливих комбінацій N = 2n+k, що дозволяє визначити необхідну кількість перевірних бітів для побудови кодів, стійких до завад.

Одним з поширених кодів, стійких до завад, які використовуються у мікропроцесорній техніці, є код з контролем на парність. У цьому коді до інформаційних бітів праворуч додається один контрольний біт (k = 1). Якщо кількість одиниць в інформаційних бітах є парною, то значення контрольного біта дорівнює 0, в протилежному випадку – 1. Отже, у будь-якому випадку кількість одиниць у повній послідовності n + 1 біт є парною. Якщо при перевірці після передачі кількість одиниць є непарною, то це означає, що має місце помилка. Код із контролем на парність дозволяє виявляти всі помилки непарної кратності і не дозволяє виявляти помилки парної кратності.

Приклад. Знайти значення контрольного біта k в кодах із контролем на парність: 1) 11000;  2) 11100.

Значення контрольного біта визначимо з умови парності кількості одиниць у послідовності із заданого коду і контрольного біта. Таким чином, значення контрольного біта k :

Іншим поширеним кодом є код Хеммінга, що виявляє і виправляє одноразові помилки. Кожній з 2n - 1 ненульових комбінацій n-розрядного числа відповідає комбінація з n + k бітів. Значення перевірних бітів отримуються в результаті додавання за модулем 2 значень бітів у деяких визначених інформаційних розрядах. Із загальної кількості 2n+k - 1 можливих помилок код Хеммінга може виявити та виправити 2k -1 помилок. Припустімо, що треба передати або обробити 15 різних послідовностей з одиниць та нулів. Без кодування для цього достатньо чотирьох інформаційних бітів (n = 4). Потрібну кількість додаткових перевірних бітів k обчислюють з формули 2k – 1 = n + к, Звідки визначають кількість перевірних розрядів та кількість одноразових помилок, які можуть бути виявлені та виправлені. У цьому випадку кількість додаткових розрядів k = 3, а кількість одноразових помилок – 2k – 1 = 7.

Контрольні біти kі розташовують у послідовності інформаційних бітів uj на позиціях із номерами 2i-1 (табл. 9.1).

Таблиця 9.1 – Послідовність контрольних та інформаційних бітів у коді Хеммінга

Значення перевірних бітів ki обчислюється додаванням за модулем 2 значень бітів, у двійковому виразі номерів яких наявна одиниця в і-му розряді.

Для обчислення значення k1 потрібно додати за модулем 2 значення бітів із непарними номерами. Це біти на позиціях з номерами 3, 5, 7, 9, 11, 13, 15:

Для визначення k2 треба додати за модулем 2 біти, у двійковому виразі номерів яких наявна одиниця  у другому розряді, тобто 3, 6, 7, 10, 11, 14, 15:

Контрольний біт k3 визначається додаванням за модулем 2 бітів, у двійковому виразі номерів яких наявна одиниця у третьому розряді, тобто 5, 6, 7, 12, 13, 14, 15:

Аналогічно визначається k4 через біти з номерами: 9, 10, 11, 12, 13, 14, 15:

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

Приклад. Сформувати код Хеммінга, що виявляє і виправляє одноразову помилку у послідовності: 

Для формування коду Хеммінга необхідно k = 3 контрольні біти, які мають займати позиції з номерами 1, 2 і 4.

Послідовність з контрольними символами має вигляд:

Значення контрольних бітів визначимо як:

Отже, послідовність, закодована за кодом Хеммінга, буде такою: 0111100.

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

Перша та друга перевірки дадуть значення 0, а третя - 1:

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