Главная | Обратная связь | Поможем написать вашу работу!

Перетворювачі кодів та схеми контролю

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

– у цифрових пристроях, ЕОМ та системах передачі даних для виявлення і корекції помилок (код з контролем на парність; код Хеммінга, циклічні коди);

– у перетворювачах аналогових фізичних сигналів у цифрові сигнали для забезпечення погрішності перетворення, що не перевищує одиниці молодшого розряду (код Грея);

– при виконанні арифметичних операцій в ЕОМ (прямий, обернений, додатковий коди); для введення в ЕОМ даних (ДДК);

– для побудови цифрових індикаторів (семисегментний код).

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

1. Перетворення вихідного двійкового коду в десятковий і наступне перетворення десяткового коду у потрібний двійковий код.

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

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

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

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

Таблиця 2.8

Код 8421	Код Грея
Х₂	Х₁	Х₀	У₂	У₁	У₀

Безпосередньо з таблиці запишемо ЛФ виходів Y₀ і Y₁ у ДДНФ:

Застосовуючи до отриманих виразів правило склеювання, маємо (у першому виразі склеюються перший і третій, другий і четвертий додаток, у другому - перший і другий, третій і четвертий):

Що стосується функції виходу Y₂, то із таблиці видно, що:

Y₂ = X₂,

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

Взагалі, схема n -розрядного перетворювача натурального двійкового коду в код Грея може бути побудована на основі наступного правила: старші розряди вхідного та вихідного кодів співпадають, а будь-який наступний розряд Y_k коду Грея дорівнює сумі по модулю двом відповідного X_k та попереднього X_k-1 розрядів натурального коду:

Узагальнений варіант УГП перетворювача кодів показаний на
рисунку 2.13 а. Чинні стандарти допускають заміну літер Х і Y позначеннями типу подання вхідної і вихідної інформації відповідно. Зокрема, для двійкового коду (стандартного) можна використовувати літеру В, для десяткового коду – скорочення DЕС, для коду Грея – G, для семисегментного коду – 7S і т.д. Таким чином, позначення синтезованого трирозрядного перетворювача може мати вигляд, зображений на рисунку 2.13б.

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

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

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

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

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

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

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

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

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

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

Іншим поширеним кодом є код Хеммінга, що виявляє і виправляє одноразові помилки. Кожній з 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, як показано у таблиці 2.9.

Таблиця 2.9

Позиція

Біт	k₁	k₂	u₁	k₃	u₂	u₃	u₄

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

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

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

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

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

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

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


u₁	u₂	u₃	u₄

Відповідно,

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


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

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

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

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

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

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

Вихідний код

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

⇐ Предыдущая 8 9 10 11 121314 15 16 17 Следующая ⇒