на головну | список тем | перегляд презинтацій | самотестування | історія створення

 

 

 

Тема 29. Розробка обчислювача контрольної суми

Різні контрольні суми широко застосовуються в цифрових пристроях і системах для контролю правильності зберігання або передачі масивів інформації. Суть цього методу контролю проста: до збереженого або передаваного інформаційного масиву приєднується невеликий контрольний код (звичайні від 1 розряду до 32 розрядів), в якому в згорнутому вигляді міститься інформація про весь масив. При читанні або отриманні цього масиву ще раз обчислюється той же самий контрольний код по тому ж самому алгоритму. Якщо цей знов обчислений код рівний тому коду, який був приєднаний до масиву, то вважається, що масив збережений або переданий без помилок. Логіка тут наступна: контрольний код (він же контрольна сума) набагато менше контрольованого масиву, тому вірогідність спотворення контрольної суми набагато менше, ніж вірогідність спотворення масиву. Якщо ж спотворяться як масив, так і контрольна сума, то вірогідність того, що ці спотворення не будуть помічені при повторному підрахунку контрольної суми, украй мала. Існує, правда, вірогідність, що масив буде спотворений в декількох місцях таким чином, що контрольна сума від цих спотворень ніяк не зміниться, але така вірогідність також звичайно мала.
Контрольні суми застосовуються при зберіганні даних в пам'яті (оперативної і постійної), при зберіганні даних на магнітних носіях (дисках, стрічках), в локальних і глобальних мережах передачі інформації. При використовуванні контрольної суми для захисту збереженої інформації можна встановити наявність або відсутність пошкоджень даного масиву (файлу, сектора на диску). При використовуванні контрольної суми для захисту передаваної по мережі інформації приймач може зажадати від передавача повторну передачу спотвореного масиву.
Існує безліч способів обчислення контрольної суми, що розрізняються ступенем складності обчислення і надійністю виявлення помилок. Але найбільше поширення набув в даний час так званий «циклічний метод контролю по надмірності» або CRC (Cyclic Redundancy Check), при якому застосовується циклічна контрольна сума.
Обчислюється циклічна контрольна сума таким чином. Весь масив інформації розглядається як одне N-розрядне двійкове число, де N - кількість біт у всіх байтах масиву. Для обчислення контрольної суми це N-разрядное число ділиться на деяке постійне число (поліном), вибране спеціальним чином (але ділиться не просто, а по модулю 2). Частка від цього поділу відкидається, а остача якраз і використовується як контрольна сума.
Ми не заглиблюватимемося в математичне обгрунтовування цього методу. Тут же ми відзначимо тільки, що даний метод виявляє одиночні помилки в масиві з вірогідністю 100%, а будь-яка інша кількість помилок з вірогідністю, зразково рівною (1-2-п ), де п - кількість розрядів контрольної суми (це вірно тільки за умови, що N набагато більше п, що, втім, майже завжди виконується). Наприклад, при п = 8 дана вірогідність складе 0,996, для п = 16 вона буде рівна 0,999985, а для п = 32 вона буде 0,9999999997672. Тобто майже всі помилки виявлятимуться.
А зараз стисло пояснимо, що таке розподіл по модулю 2. Хай масив (послідовність біт) має наступний вигляд: 101111001110 (для простоти беремо невелику розрядність). Як дільник (що зветься звичайно поліномом) візьмемо число 10011. Як воно вибирається? Воно повинне ділитися по модулю 2 без остачі тільки на одиницю і саме на себе (тобто це повинне бути просте число в значенні розподілу по модулю 2). Розрядність полінома береться на одиницю більша, ніж необхідна розрядність контрольної суми ( остачі  від розподілу). Так, щоб одержати 8-розрядну остачу (8-розрядну контрольну суму), треба брати 9-розрядний поліном. В нашому випадку поліном 5-розрядний, отже, остачі буде 4-розрядною. Для отримання 8-розрядної остачі можна використовувати, наприклад, поліном 1 0001 1101 або 1 ID в 16-ковому коді.
Розподіл по модулю 2 проводиться точно так, як і звичний для нас розподіл «в стовпчик» (малюнок 29.1), але замість віднімання в даному випадку використовується порозрядне додавання по модулю 2, тобто кожний результуючий біт є функцією що Виключного АБО від відповідних бітів складових. Частка від розподілу нас не цікавить, а остача, рівна в нашому прикладі 1000, і буде циклічною контрольною сумою.

tf

Малюнок 29.1. Обчислення циклічної контрольної суми.

Як практично реалізувати обчислення цієї остачі (контрольної суми)? Можна зробити це за приведеним тут принципом розподілу в стовпчик (апаратно або програмно). Але у будь-якому випадку це досить громіздко і повільно. Прискорити процес обчислення можна, скориставшися табличним методом. Для цього складається таблиця чисел розміром 2n*п, де п - розрядність контрольної суми. Принцип обчислення чисел в таблиці дуже простий (таблиця 29.1).

yu

Числа є остачею від розподілу по модулю 2 числа з п кінцевими нулями (в нашому прикладі п = 8) і з п початковими розрядами, рівними номеру числа (його адресі) в таблиці. Розподіл проводиться на вибраний поліном (в нашому випадку - 9-розрядний). Таблиця обчислюється один раз і зберігається на диску або в ПЗП.
Алгоритм обчислення контрольної суми за допомогою цієї таблиці наступний (розглядаємо випадок п = 8). Беремо перший байт нашого інформаційного масиву. Розглядаємо його як адресу в таблиці (номер числа). Беремо з таблиці число з одержаним номером - одержуємо остачу O1. Беремо другий байт масиву і складаємо його по модулю 2 із остачею О1 Одержане число використовуємо як адресу в таблиці. За цією адресою вибираємо з таблиці остачу О2. Беремо третій байт масиву, складаємо його по модулю 2 із остачею О2. Використовуючи це число як адресу в таблиці, вибираємо з неї остачу Оз і так продовжуємо до останнього байта масиву. Природно, це буде набагато швидше, ніж обчислення «в стовпчик».

yf

Малюнок 29.2. Паралельний обчислювач 8-розрядної циклічної контрольної суми на ПЗП.

Для реалізації цього алгоритму за допомогою цифрових схем потрібен тільки ПЗП з організацією 2п*п (256 X 8 при 8-розрядній контрольній сумі), n-розрядний регістр і п елементів Виключного АБО (малюнок 29.2). В ПЗП заноситься таблиця проміжних залишків (таблиця 29.1), на вхід схеми подаються один за іншим байти масиву, супроводжувані стробом. Адресою ПЗП служить сума по модулю 2 вхідних даних і вмісту вихідного регістра, в який по сигналу строба записується вихідний код ПЗП. Перед початком обчислення стан регістра обнуляється. Після закінчення всього масиву в регістрі утворюється циклічна контрольна сума.
Недолік даної схеми паралельного обчислювачаочевидний:у випадку великого числа розрядів контрольної суми потрібен дуже великий об'єм ПЗП. Тому вона застосовується порівняно рідко. Зате паралельний обчислювач володіє високою швидкодією (байти можуть поступати з періодом, рівним сумі затримки вихідного регістра, часу вибірки адреси ПЗП і затримки елемента Виключного АБО).
Для багаторозрядної контрольної суми частіше застосовується інший підхід - обчислення в послідовному коді, при якому на обчислювач масив даних поступає послідовно, біт за бітом. Послідовний обчислювач контрольної суми є зсувним регістром із зворотними зв'язками від деяких розрядів через суматори по модулю 2 (тобто елементи Виключне АБО). Повна кількість розрядів регістра зсуву повинна бути рівною розрядності обчислюваної контрольної суми (або, що те ж саме, бути на одиницю менше розрядності полінома, що використовується). Місце включення зворотних зв'язків однозначно визначається вибраним поліномом.
Кількість точок включення зворотного зв'язку визначається кількістю одиниць в поліномі (одиниця в молодшому розряді не враховується), а номери розрядів зсувного регістра, з яких беруться сигнали зворотного зв'язку, визначаються номерами одиничних розрядів в коді полінома. На відміну від генератора квазівипадкового сигналу в даному випадку необхідно змішати по функції те, Виключного АБО не тільки сигнали зворотного зв'язку, але і вхідний сигнал даних в послідовному коді.
На малюнку 29.3 приведений приклад послідовного обчислювача 16-розрядної циклічної контрольної суми при вибраному поліномі 1 0001 0000 0010 0001 або 11021 в 16-ковому коді. Оскільки в коді полінома три одиниці (без молодшого розряду), необхідно узяти три точки включення зворотного зв'язку. При цьому номери розрядів зсувного регістра, до яких підключаються зворотні зв'язки, визначаються положенням одиничних бітів в поліномі. Перед початком роботи зсувний регістр необхідно скинути в нуль (сигнал -Сброс). Біти масиву повинні супроводжуватися сигналом строба. Після закінчення масиву в регістрі буде циклічна контрольна сума.

f

Малюнок 29.3. Послідовний обчислювач 16-розрядної циклічної контрольної суми на регістрі зсуву.

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

попередня тема до списку тем