47385 (597334), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Рис. 4. Перетворювач натурального двійкового коду у код Грея

а) б)

Рис. 5. УГП перетворювачів кодів : а – загальне позначення,
б – позначення трирозрядного перетворювача натурального коду у код Грея

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

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

Неважко помітити, що алгоритм отримання додаткового контрольного біту для n-розрядного паралельного кодового слова співпадає з логічною функцією „виключне АБО” n аргументів.

Схема отримання контрольного біта Р також може бути реалізована на суматорах за модулем 2 (елементах „виключне АБО” на 2 входи). У цьому разі схема будується за багатоярусним принципом: спочатку попарно додаються значення окремих розрядів кодового слова, потім отримані результати також попарно додаються за допомогою суматорів за модулем 2 другого ярусу і т.д., наприклад:

Багатоярусні схеми на суматорах за модулем 2 часто називають схемами згортки. На рис. 6 зображена схема отримання двійкового коду з контролем на парність, де схема згортки позначена прямокутником з написом 2k+1.

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

Очевидно, що схема, яка перевіряє на парність прийняті кодові слова (схема контролю на парність), також являє собою логічний елемент „виключне АБО” n + 1 аргументів (з урахуванням контрольного біта), або багатоярусну схему на суматорах за модулем 2, яку часто називають схемою згортки.

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

Додатковий матеріал для самостійного вивчення: (Тиртишніков О.І., Корж Ю.М. Обчислювальна техніка та мікропроцесори. Частина 2. Цифрові автомати: Навчальний посібник. – Полтава: ПВІЗ, 2006, с. 25 – 28.

Іншим поширеним кодом є код Хеммінга, що виявляє і виправляє одноразові помилки. Кожній з 2ⁿ-1 ненульових комбінацій n-розрядного кодового слова відповідає комбінація з n + k бітів. Значення контрольних бітів отримують в результаті додавання за модулем 2 значень бітів у деяких визначених інформаційних розрядах. Із загальної кількості 2^n+k-1 можливих помилок код Хеммінга може виявити та виправити 2^k-1 помилок.

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

Контрольні біти k_i розташовують у послідовності інформаційних бітів u_j на позиціях із номерами 2^i-1, як показано у табл. 5.

Таблиця 5

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

.

Для визначення k₂ треба додати за модулем 2 біти, у двійковому виразі номерів яких наявна одиниця у другому розряді, тобто:

.

Контрольний біт k₃ визначається додаванням за модулем 2 бітів, у двійковому виразі номерів яких наявна одиниця у третьому розряді:

.

Схема перетворювача чотирирозрядних кодових слів у код Хеммінга зображена на рис. 7.

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

Рис. 7. Схема перетворювача чотирирозрядних кодових слів в код Хеммінга

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

Відповідно,

Послідовність, що закодована кодом Хеммінга, буде мати вигляд:

0	1	1	1	1	0	0
k1	k2	u1	k3	u2	u3	u4

Нехай після передачі відбувся збій в одному розряді і прийнята послідовність 0110100 (помилка в четвертому розряді – k₃). Тоді перша та друга перевірки дадуть значення 0, а третя – 1:

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

Із розглянутого прикладу видно, що схема пристрою контролю повинна містити такі складові частини: схеми згортки (елементи „виключне АБО”) відповідно кількості перевірок, що виконуються; дешифратор, який на основі отриманого синдрому керує інверсією помилкового розряду та елементів, що виконують саму інверсію. Така схема зображена на рис. 16 (схеми згортки позначені прямокутником з написом 2k + 1). У якості „керованих інверторів” у схемі використовуються суматори за модулем 2.

Вихідний код

k₁k₂u₁k₃u₂u₃u₄

Рис. 16. Схема пристрою контролю

Характеристики

Список файлов книги