7.6.5. Системи контролю цифрової апаратури

Вузли ділення поліномів використовують також при контролі правильності роботи логічних схем методом сигнатурного аналізу. На входи схеми, що перевіряється, з генератора псевдовипадкових чисел подається визначеної довжини та завжди однакова послідовність псевдовипадкових чисел. Вихідна тестова послідовність проходить через поліномінальний розподілювач, який ділить її на достатньо складний поліном G. Поліномінальний розподілювач називають сигнатурним аналізатором. Залишок, який залишається в регістрі поліномінального розподілювача після закінчення вихідної тестової послідовності, називають сигнатурою. На виході справної цифрової системи сигнатура від заданої цифрової тестової послідовності завжди заздалегідь відома і може бути розпізнана, наприклад, за допомогою компаратора. Сигнатура несправної системи інша, причому, завдяки процедурі ділення та складному поліному G, будь-яка незначна відмінність значно посилюється. На теперішній час широке використання отримав шістнадцятирозрядний аналізатор. Частка помилок, котра ним не виявляється, оцінюється величиною 2^–16.

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

Зупинимося коротко на ще одному методі тестової перевірки працездатності цифрових схем з використанням цифрових регістрів, який в вітчизняній практиці зветься методом наскрізного зсувного регістра, або методом сканування []. Суть цього методу полягає у наступному. Для повного контролю складних цифрових схем необхідно мати доступ до великої кількості контрольних точок, які повинні бути виведені на роз’єми відповідних плат, або до виводів ВІС. Однак для цього повинна бути велика кількість виводів, що у більшості випадків забезпечити неможливо. У зв’язку з цим в якості контрольних точок зручно використовувати виводу тригерів. З’єднуючи всі тригери аналізованої схеми (а у ряді випадків – і додаткові зовнішні тригери) в один зсувний регістр, можливо послідовним кодом вводити тестову інформацію, що аналізує контрольні точки. Зазвичай для вирішення цієї задачі використовується третій стан мікросхем, тригери відключаються від основної схеми та заводяться спеціальні серії синхросигналів. Перевірка працездатності наскрізного регістра здійснюється за допомогою генераторів псевдовипадкових послідовностей та сигнатурних аналізаторів [].

7.6.6. Використання регістрів для обчислення контрольної суми

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

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

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

Серед способів обчислення контрольної суми найбільшого поширення набув циклічний спосіб контролю за надлишковістю (CRC – Cycle Redundancy Check), при якому використовується циклічна контрольна сума. Обчислюється вона у такий спосіб. Весь контрольований масив інформації розглядається як одне N-розрядне двійкове число. Це число ділиться за модулем 2 на постійний поліном. Залишок від ділення використовується в якості контрольної суми.

Приклад 7.8. Обчислити контрольну суму для масиву 101111001110 при використанні поліному 10011.

Розв’язання. Ділення за модулем 2 виконується в тій самій послідовності, що і звичайне ділення двійкових чисел (див. Розділ І) з тією лише різницею, що замість операції віднімання виконується операція додавання за модулем 2. Операцію ділення виконаємо в стовпчик.

	1	0	1	1	1	1	0	0	1	1	1	0	1	0	0	1	1	Поліном
	1	0	0	1	1
	0	0	1	0	0	1	0
			1	0	0	1	1
			0	0	0	0	1	0	1	1	1
							1	0	0	1	1
							0	0	1	0	0	0		Залишок (контрольна сума)

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

Вибір поліному для обчислення контрольної суми однозначно пов’язаний із заданою ймовірністю виявлення помилок. Розглянутий спосіб виявляє одиночні помилки у контрольованому масиві з ймовірністю 1, а будь-яку іншу кількість помилок – з ймовірністю, що приблизно визначається формулою:

P = 1 – 2^–n ,

де n – кількість розрядів контрольної суми.

Як приклад, для n = 8 – P = 0,996; для n = 16 – P = 0,999985, а для n = 32 – P = 0,999999999767.

З приведеного прикладу можна помітити таку особливість залишку: він має розмірність на один розряд меншу, ніж розмірність поліному. Це не випадковість. Можна взяти масив будь-якої довжини, і результат (залишок) також матиме довжину на один розряд меншу довжини поліному. Таким чином, вибравши ймовірність виявлення помилок, обчислюється розмір контрольної суми і, відповідно, розмір поліному. Другою вимогою до поліному є те, щоб він був простим числом з точки зору ділення за модулем 2 (вибраний поліном повинен ділитися лише на 1 і на самого себе).

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

Послідовний обчислювач контрольної суми виконується на регістрі зсуву зі зворотними зв’язками від деяких розрядів через суматори за модулем 2. Повна кількість розрядів регістра зсуву повинна бути рівною розрядності контрольної суми, що обчислюється. Місце підключення зворотних зв’язків однозначно визначається вибраним поліномом (згадайте генератори псевдовипадкових послідовностей). Кількість з’єднань для створення зворотного зв’язку визначається кількістю одиниць в поліномі (одиниця молодшого розряду не враховується), а номери розрядів регістра зсуву, з яких беруться сигнали зворотних зв’язків, визначаються номерами одиничних розрядів у коді поліному. На відміну від генератора псевдовипадкових послідовностей, у даному випадку необхідно змішувати по функції ВИКЛ. АБО не тільки сигнали зворотних зв’язків, а й вхідний сигнал даних у послідовному коді.

На рис. 7.41 приводиться приклад схеми пристрою для послідовного обчислення шістнадцятирозрядної циклічної контрольної суми при поліномі 1 0001 0000 0010 0001. Оскільки в коді поліному наявні три одиниці (за виключенням молодшого розряду), то необхідно вибрати три лінії зворотних зв’язків з розрядів регістра, відповідні положенням одиничних бітів у поліномі.

Рис. 7.41

Перед початком роботи регістр встановлюється у нуль (Уст. “0”). Біти масиву супроводжуються синхросигналом. По закінченню масиву в регістр буде записана контрольна сума, яка серією синхросигналів буде виведена вслід за бітами масиву. Швидкодія даного пристрою обмежується сумарною затримкою регістра та елементів ВИКЛ. АБО, яка повинна бути меншою періоду синхросигналів.