Полтавський Військовий ІнститутЗв’язку
Кафедрасхемотехніки радіоелектронних системОБЧИСЛЮВАЛЬНА ТЕХНІКА ТАМІКРОПРОЦЕСОРИ
напрямпідготовки 0924 «Телекомунікації»
Компаратори слів, перетворювачі кодів та схеми контролю.
Полтава– 2006
Навчальна література.
1. ТиртишніковО.І., Корж Ю.М. Обчислювальна техніка та мікропроцесори. Частина 2. Цифровіавтомати: Навчальний посібник. – Полтава: ПВІЗ, 2006, с. 20 – 33.
2. КалабековБ.А., Мамзелев И.А. Цифровые устройства и микропроцессорные системы. М.: Радиои связь, 1987.
1.Компаратори слів (схеми порівняння).
Компараторислів(схемипорівняння) – це комбінаційні цифрові вузли, які виконують функцію порівняннядвох кодових слів визначеної розрядності. Основними операціями, що виконуються схемамипорівняння, є визначення ознаки рівності або нерівності двох n-розряднихчисел, причому операція порівняння може супроводжуватися визначенням знаканерівності.
Розглянемо синтезсхеми порівняння двох трирозрядних кодових слів X2X1X0і Y2Y1Y0, яка має три виходи (Y=X,Y>X, Y), за умови, що активний рівень сигналів – логічна 1.
Таблицяістинності схеми буде мати вигляд:
Таблиця 1
№ набору
X2
X1
X0
Y2
Y1
Y0
Y=X
Y
Y>X 1 1 1 1 2 1 1 ... ... ... ... ... ... ... … … … 56 1 1 1 1 57 1 1 1 1 1 ... ... ... ... ... ... ... … … … 63 1 1 1 1 1 1 1
Очевидно, щосинтез схеми традиційним методом – з поданням вихідних функцій у вигляді ДДНФта подальшою їх мінімізацією буде занадто складним, оскільки потребуємінімізації трьох функцій шести змінних. Тому виконаємо синтез схеми звикористанням евристичних прийомів та без визначення обмежень на застосуванняелементів тих чи інших типів.
По-перше,очевидно, що схема, яка виконує функцію Y = X, може бути реалізованапорозрядним порівнянням слів X2X1X0 та Y2Y1Y0,за допомогою елементів рівності та елемента „ТА” (якщо всі розряди двох кодовихслів попарно дорівнюють один одному, то і кодові слова в цілому еквівалентні).Відповідна схема зображена на рис. 1.
По-друге,будь-яка з трьох вихідних функцій може бути виражена через дві інші. Наприклад,якщо Y не менше X та Y не дорівнює X, то Y >X. Це твердження можна подати таблицею істинності (табл. 2). Отриманатаблиця істинності може бути реалізована елементом АБО-НІ на два входи, якпоказано на рис. 2.
Таблиця 2
Вхідні функції
Вихідна функція
Y=X
Y
Y>X 1 1 1 1 1
Таким чином,залишилося синтезувати схему, яка буде реалізувати функцію Y Вонаможе бути отримана на підставі наступного твердження: для того, щоб однекодове слово було більше, ніж друге, достатньо, щоб старший розряд першогослова був більшим, ніж старший розряд другого, або щоб будь-який розряд першогослова був більшим відповідного розряду другого слова за умови, що старшірозряди обох слів попарно рівні.
Функціяпорівняння відповідних окремих розрядів двох кодових слів за умови Xn >Yn може бути отримана на підставі таблиці істинності (табл. 3).
X1Y1X2Y2X3Y3
/> />/> /> /> /> />
Рис. 1. Схема, що виконує функцію Y = X
Рис. 2. Схема, що виконує функцію Y > X
Таблиця 3
X
Y
FX>Y 1 1 1 1 1 />
/>
Таким чином,схема порівняння відповідних окремих розрядів двох кодових слів, за умови X> Y, являє собою елемент ТА, а результати порівняння старших розрядівкодових слів, за умови Y = X, можуть бути отримані з виходів відповіднихелементів рівності схеми, що зображена на рис.1.
Трирозрядна схемапорівняння відповідних розрядів двох кодових слів, за умовою X >Y,повинна реалізовувати логічну функцію
FX>Y= F1 + F2 + F3,
де:
/>
Так як у схемахпорівняння окремих розрядів вхідних кодових слів використовуються інверсіїрозрядів слова Y, доцільно для зменшення загальної кількості входівсхеми перетворити схему, що виконує функціюY = X (рис. 1) таким чином,щоб вона також використовувала інверсії розрядів слова Y як вхідніаргументи. Це може бути зроблено наступним чином:
/>.
Тобто в схемі, щовиконує функціюY = X, будуть використовуватися замість елементіврівності суматори за модулем 2.
Отримана схемакомпаратора трирозрядних кодових слів зображена на рис. 3.
/> />
/>
Рис.3. Схема компаратора трирозрядних кодових слів
2.Перетворювачі кодів та схеми контролю.
2.1.Перетворювачі кодів.
У цифрових пристроях частовиникає необхідність перетворення інформації з одного двійкового коду в інший.Коди, що відрізняються від найбільш простого натурального 8421, наприклад,застосовуються:
— уцифрових пристроях, ЕОМ та системах передачі даних для виявлення і корекціїпомилок (код з контролем на парність; код Хеммінга, циклічні коди);
— уперетворювачах аналогових фізичних сигналів у цифрові сигнали для забезпеченняпогрішності перетворення, що не перевищує одиниці молодшого розряду (код Грея);
— привиконанні арифметичних операцій в ЕОМ (прямий, зворотний, додатковий коди); длявведення в ЕОМ даних (ДДК);
— дляпобудови цифрових індикаторів (семисегментний код).
Для синтезу перетворювачівкодів можна користуватися двома методами.
1. Перетворення вихідногодвійкового коду в десятковий і наступне перетворення десяткового коду унеобхідний двійковий код.
2. Використаннякомбінаційного логічного пристрою, що безпосередньо реалізовує необхіднеперетворення.
Перший метод структурнореалізовується з'єднанням дешифратора і шифратора і є зручним у випадках, колиможна використовувати стандартні дешифратори і шифратори в інтегральномувиконанні. Використання другого методу нерідко зменшує апаратні витрати на реалізаціюперетворювача.
Розглянемо синтезперетворювача другим методом на прикладі трирозрядного перетворювачанатурального двійкового коду код Грея, що також називають циклічним аборефлексно-двійковим.
Особливістю коду Грея є те,що в ньому кодові комбінації двох сусідніх чисел відрізняються тільки в одномудвійковому розряді. Відповідність трирозрядних двійкових чисел їх кодам Греяпоказано в таблиці 4.
Таблиця 4
Код 8421
Код Грея
Х2
Х1
Х0
У2
У1
У0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Безпосередньо з таблицізапишемо функції виходів Y0 і Y1 у ДДНФ. Щостосується функції виходу Y2, із таблиці видно, що Y2= X2.
/>
/>
Застосовуючи до отриманихвиразів правило склеювання, маємо (у першому виразі склеюються перший і третій,другий і четвертий додаток, у другому — перший і другий, третій і четвертий):
/>
/>
Таким чином, найпростішеданий перетворювач реалізовується на двох суматорах по модулю два. Відповіднасхема зображена на рис. 4.
Взагалі,схема n-розрядного перетворювача натурального двійкового коду в код Греяможе бути побудована на основі наступного правила: старші розряди вхідного тавихідного кодів співпадають, а будь-який наступний розряд Ykкоду Грея дорівнює сумі по модулю два відповідного Xk тапопереднього Xk-1 розрядів натурального коду:
/>
Узагальнений варіант УГПперетворювача кодів показаний на рис. 5а. Чинні стандарти допускають замінулітер Х і Y позначеннями типу подання вхідної і вихідноїінформації відповідно. Зокрема, для двійкового коду (стандартного) можнавикористовувати літеру В, для десяткового коду скорочення DЕС,для коду Грея – G, для семисегментного коду 7S і т.д. Такимчином, позначення синтезованого трирозрядного перетворювача може мати вигляд,зображений на рис. 5б.
Поняттяпро кодування, захищене від завад.
Унаслідок дії завад під часпередачі, обробки та збереження двійкових кодів у МПС можуть статися помилки,наприклад, прийом 1 замість 0 або навпаки. Це може привести до неправильногорезультату роботи МПС.
Одним з найбільш ефективнихшляхів захисту інформації у МПС є кодування, стійке до завад, яке здійснюєтьсявведенням у кодові слова додаткових бітів, призначених або для виявлення івиправлення помилок, або тільки для виявлення помилок. Відповідно до цьогокоди, стійкі до завад, поділяють на коректувальні коди, які виявляють івиправляють помилки, та коди, які тільки виявляють помилки.
/>
Рис. 4.Перетворювач натурального двійкового коду у код Грея
/>
а) б)
Рис. 5. УГПперетворювачів кодів: а – загальне позначення,
б – позначення трирозрядного перетворювача натурального коду у код Грея
Можливість виявлення помилокза наявності додаткових бітів обумовлена тим, що для передачі інформаціївикористовуються не всі можливі комбінації n-розрядного двійкового коду,а лише деяка частина з них. Дозволені комбінації вважаються безпомилковими,інші є забороненими. Поява заборонених комбінацій розглядається як помилка.Слід уявляти, що можливі такі помилки, за яких одна дозволена комбінаціяпереходить у іншу. У цьому випадку помилки не виявляються.
Найпростішим поширеним кодом,стійким до завад, який використовується у мікропроцесорній техніці, є код зконтролем на парність. У цьому коді до інформаційних бітів праворуч додаєтьсяодин контрольний біт. Якщо кількість одиниць в інформаційних бітах є парною, тозначення контрольного біта дорівнює 0, у протилежному випадку – 1. Отже, у будь-якомувипадку кількість одиниць у повній послідовності (кодовому слові з контрольнимбітом) є парною. Якщо при перевірці після передачі кількість одиниць єнепарною, то це означає, що відбулася помилка. Код із контролем на парністьдозволяє виявляти всі помилки непарної кратності (у одному біту кодового слова)і не дозволяє виявляти помилки парної кратності (у двох бітах кодового словаодночасно).
Неважко помітити, що алгоритмотримання додаткового контрольного біту для n-розрядного паралельногокодового слова співпадає з логічною функцією „виключне АБО” nаргументів.
Схема отриманняконтрольного біта Р також може бути реалізована на суматорах за модулем 2(елементах „виключне АБО” на 2 входи). У цьому разі схема будується забагатоярусним принципом: спочатку попарно додаються значення окремих розрядівкодового слова, потім отримані результати також попарно додаються за допомогоюсуматорів за модулем 2 другого ярусу і т.д., наприклад:
/>
Багатояруснісхеми на суматорах за модулем 2 часто називають схемами згортки. На рис. 6зображена схема отримання двійкового коду з контролем на парність, де схемазгортки позначена прямокутником з написом 2k+1.
/>
Рис.6. Схема отримання двійкового коду з контролем на парність
Очевидно, щосхема, яка перевіряє на парність прийняті кодові слова (схема контролю напарність), також являє собою логічний елемент „виключне АБО” n + 1аргументів (з урахуванням контрольного біта), або багатоярусну схему насуматорах за модулем 2, яку часто називають схемою згортки.
Висновок: аналізуючи схемиперетворювачів кодів та схем контролю, які були розглянути вище, неважкопомітити, що в більшості з них використовуються суматори за модулем 2, абосхеми згортки, побудовані на основі цих суматорів.
Додатковийматеріал для самостійного вивчення: (Тиртишніков О.І., Корж Ю.М. Обчислювальна техніка тамікропроцесори. Частина 2. Цифрові автомати: Навчальний посібник. – Полтава:ПВІЗ, 2006, с. 25 – 28.
Іншим поширенимкодом є код Хеммінга, що виявляє і виправляє одноразові помилки. Кожній з 2n-1ненульових комбінацій n-розрядного кодового слова відповідає комбінаціяз n + k бітів. Значення контрольних бітів отримують в результатідодавання за модулем 2 значень бітів у деяких визначених інформаційнихрозрядах. Із загальної кількості 2n+k-1 можливих помилок кодХеммінга може виявити та виправити 2k-1 помилок.
Припустимо, щотреба передати або обробити 15 різних двійкових повідомлень. Без кодування дляцього достатньо чотирьох інформаційних бітів (n = 4). Потрібнукількість додаткових контрольних бітів обчислюють за формулою 2k-1= n + k. Звідки визначають кількість перевірних розрядів та кількістьодноразових помилок, які можуть бути виявлені та виправлені. У цьому випадкукількість додаткових розрядів k = 3, а кількість одноразовихпомилок – 2k-1 = 7.
Контрольні біти kiрозташовують у послідовності інформаційних бітів ujнапозиціях із номерами 2i-1, як показано у табл. 5.
Таблиця 5Позиція 1 2 3 4 5 6 7 001 010 011 100 101 110 111 Біт
k1
k2
u1
k3
u2
u3
u4
Значенняперевірних бітів ki обчислюється додаванням за модулем 2значень бітів, у двійковому виразі номерів яких наявна одиниця в i-мурозряді. Відповідно, для обчислення значення k1 потрібнододати за модулем 2 значення бітів із непарними номерами:
/>.
Для визначення k2треба додати за модулем 2 біти, у двійковому виразі номерів яких наявна одиницяу другому розряді, тобто:
/>.
Контрольний біт k3визначається додаванням за модулем 2 бітів, у двійковому виразі номерів якихнаявна одиниця у третьому розряді:
/>.
Схемаперетворювача чотирирозрядних кодових слів у код Хеммінга зображена на рис. 7.
Визначення тавиправлення помилок здійснюється k перевірками. При кожній перевірцідодаються за модулем 2 біти прийнятої послідовності інформаційних таконтрольних розрядів, двійкові номера яких мають одиницю в першому, другому ітак далі розрядах. Якщо під час передавання не було збою, то результати всіхперевірок дорівнюють нулю. Якщо збій відбувся, то хоча б одна перевірка недорівнює нулю. У цьому випадку треба сформувати кодову комбінацію з результатівперевірок, який вкаже на розряд, де відбувся збій (він має назву синдром).Молодший розряд коду результатів перевірок формує перша перевірка, старший –остання. Інверсія біта в розряді з одержаним номером виправить помилку.
/>
Рис.7. Схема перетворювача чотирирозрядних кодових слів в код Хеммінга
Наприклад,необхідно сформувати код Хеммінга, що виявляє та виправляє одноразові помилки упослідовності:1 1
u1
u2
u3
u4
Відповідно,
/>
/>
/>
Послідовність, щозакодована кодом Хеммінга, буде мати вигляд: 1 1 1 1
k1
k2
u1
k3
u2
u3
u4
Нехай післяпередачі відбувся збій в одному розряді і прийнята послідовність 0110100(помилка в четвертому розряді – k3). Тоді перша та другаперевірки дадуть значення 0, а третя – 1:
/>
/>
/>
Код 100, щостворюють результати перевірок, вказує, що відбувся збій у четвертому розряді.Якщо проінвертувати четвертий розряд, то одержимо виправлену послідовність0111100.
Із розглянутогоприкладу видно, що схема пристрою контролю повинна містити такі складовічастини: схеми згортки (елементи „виключне АБО”) відповідно кількостіперевірок, що виконуються; дешифратор, який на основі отриманого синдрому керуєінверсією помилкового розряду та елементів, що виконують саму інверсію. Такасхема зображена на рис. 16 (схеми згортки позначені прямокутником з написом 2k+ 1). У якості „керованих інверторів” у схемі використовуються суматориза модулем 2.
k1k2u1k3u2u3u4
Вихідний код />
Рис. 16. Схема пристрою контролю