Теорія операційної системи

:: Меню ::

Головна
Представлення даних в обчислювальних системах
Машинні мови
Завантаження програм
Управління оперативною пам'яттю
Сегментна і сторінкова віртуальна пам'ять
Комп'ютер і зовнішні події
Паралелізм з точки зору програміста
Реалізація багатозадачності на однопроцесорних комп'ютерах  
Зовнішні пристрої
Драйвери зовнішніх пристроїв
Файлові системи
Безпека
Огляд архітектури сучасних ОС

:: Друзі ::

Карта сайту
 

:: Статистика ::

 

 

 

 

 

Контрольні суми

Зберігання даних і їх передача часто супроводиться або може супроводитися помилками. Приймачу і передавачу інформації необхідно знати, що дані в потоці повинні відповідати певним правилам. Приводячи реальний потік у відповідність з цими правилами, приймач може відновити його вихідний вміст. Кількість і типи практично відновлених помилок визначаються вживаними правилами кодування. Зрозуміло, що завжди існує (і у багатьох випадках може бути теоретично оцінений) поріг кількості помилок в повідомленні, після якого повідомлення не піддається навіть частковому відновленню.
Відповідність потоку даних тим або іншим правилам теорія інформації описує як наявність статистичних автокореляцій або інформаційної надмірності в потоці. Такі дані завжди матимуть більший об'єм, чим еквівалентні, але не відповідні жодним правилам (наприклад, упаковані), тобто перешкодозахищена досягається не безкоштовно. Існування "безкоштовних" засобів підвищення перешкодозахищеної каналів протіворечит, ні багато, ні мало, Другому Початку термодинаміки (доказ цього твердження вимагає глибоких знань в області теорії інформації і термодинаміки, і тому тут не приводиться).
Природні мови забезпечують дуже високу (у письмовій формі Двух- і трикратну, а в звуковій ще більшу) надмірність за рахунок вживання складних фонетичних, лексичних і синтаксичних правил. Дотепним способом додаткового підвищення надмірності людської мови є вірші (білі і, тим більше, римовані), що широко використалися до винаходу писемності для підвищення надійності зберігання в людських же головах історичних відомостей і священних текстів.
На жаль, із завданням відновлення спотворених повідомлень на природних мовах в спільному випадку може впоратися лише людський мозок. Правила кодування, застосовні в обчислювальних системах, повинні задовольняти не лише вимогам теоретико-інформаційній оптимальності, але і бути досить прості для програмної або апаратної реалізації.
Простим способом внесення надмірності є повне дублювання даних. Завдяки своїй простоті, цей спосіб інколи застосовується ні практиці, але володіє багаточисельними недоліками. По-перше, надмірність цього методу надмірно висока для багатьох практичних вживань. По-друге, він дозволяє лише виявляти помилки, але не виправляти їх: за відсутності інших правил кодування, ми не можемо знати, яка з копій вірна, а яка помилкова.
Триразове копіювання забезпечує ще вищу надмірність, зате при його використанні для кожного біта, що розходиться, ми можемо проводити голосування: вважати за правильне те значення, яке присутнє мінімум в двох копіях даних (в даному випадку ми виходимо з того, що вірогідність помилки в одному і тому ж біті двох копій досить мала).
Трикратне копіювання, таким чином, дозволяє відновлювати дані, але має дуже вже високу надмірність. Ці приклади, окрім простоти, цікаві -тем, що демонструють нам практично важливу класифікацію надлишкових код: бувають коди, які лише виявляють помилки, а бувають і такі, які дозволяють їх відновлювати. Далеко не завжди коди другого типа можуть бути побудовані на основі код першого типа. У багатьох випадках, наприклад при передачі даних по мережі, доцільно запитати повтор зіпсованого пакету, тому коди, здатні лише виявляти помилки, практично корисні і широко застосовуються.
Всі дані, з якими можуть працювати сучасні обчислювальні системи, є послідовностями бітів, тому всі правила, які ми далі розглядатимемо, поширюються лише на таких последовател ьності.
Простий з вживаних способів кодування з виявленням помилок — це біт парності . Блок даних забезпечується додатковим бітом, значення якого вибирається так, щоб загальна кількість бітів, рівних одиниці, в блоці було парним. Такий код дозволяє виявляти помилки в одному біті блоку, але не в двох бітах (строго кажучи — дозволяє виявляти непарну кількість помилкових бітів). Якщо вірогідність помилки в двох бітах досить велика, нам слід або розбити блок на два блоки меншого розміру, кожен зі своїм бітом парності, або використовувати складніші схеми кодування.
Найпоширеніша з таких складніших схем — це CRC (Cyclic Redundancy Code, циклічний надлишковий код). При обчисленні CRC розрядності N вибирають число R необхідної розрядності і обчислюють залишок від ділення на R блоку даних (що розглядається як єдине двійкове число), зрушеного вліво на N бітів. Двійкове число, утворене блоком даних і залишком, ділиться на R, і цей факт можна використовувати для перевірки цілісності блоку (але не для відновлення даних при помилці!).
Здатність контрольної суми виявляти помилки логічніше вимірювати не в кількості помилкових бітів, а у вірогідності невиявлення помилки. При використанні CRC проходитимуть непоміченими лише поєднання помилок, що задовольняють вельми спеціальній умові, а саме такі, вектор помилок (двійкове число, одиничні біти якого відповідають помилковим бітам прийнятого блоку, а нульові — правильно прийнятим) яких ділиться на R. При випадковому розподілі помилок вірогідність цього може бути грубо оцінена як 1/r, тому збільшення розрядності контрольної суми у поєднанні з вибором простих R забезпечує досить швидкий і дешевий спосіб перевірки цілісності навіть досить довгих блоків. 32- розрядний CRC забезпечує практично повну гарантію того, що дані не були пошкоджені, а 8-розрядний — упевненість, достатню для багатьох цілей. Проте ні парність, ні CRC не можуть нам нічим допомогти при відновленні пошкоджених даних.
Простий метод кодування, що дозволяє не лише виявляти, але і виправляти помилки, називається блоковою або паралельною парністю і полягає в тому, що ми записуємо блок даних у вигляді двомірної матриці і підраховуємо біт парності для кожного рядка і кожного стовпця. При одиночній помилці, таким чином, ми легко можемо знайти біт, який псує нам життя. Подвійні помилки така схема кодування може виявляти, але не здатна відновлювати (мал. 1.9).

Мал. 1.9. Паралельна парність

Широко відомий і вживаний код Хеммінга (Hamming code) знаходиться в близькій спорідненості з паралельною парністю. Його теоретичне обгрунтування декілька менш очевидно, чим в попереднього алгоритму, але в реалізації він, мабуть, навіть простіше [Берлекемп 1971]. Ідея алгоритму полягає в тому, щоб забезпечити блок даних декількома бітами парності, підрахованими по різних совокупностям бітів даних. При виконанні нерівності Хеммінга (1.1) сформований таким чином код забезпечує виявлення і виправлення одиночних помилок або гарантоване виявлення (але не виправлення!) подвійних помилок. Поважно підкреслити гарантію виявлення, на відміну від всього лише високій вірогідності виявлення при використанні CRC.

d + р+1<= 2р, (1.1)

де d — кількість бітів даних р — розрядність контрольної коди.
Код, що використовує d і р при яких вираження (1.1) перетворюється на рівність, називають оптимальним кодом Хеммінга.
Часто виявляється доцільно поєднувати упаковку даних з їх надлишковим кодуванням. Найбільш вдалим прикладом такої доцільності знову-таки є тексти на природних мовах: статистичний аналіз такого тексту показує дуже високий, більш ніж двократний, рівень надмірності. З одного боку, це дуже багато для більшості практично вживаних способів цифрової передачі і кодування даних, а з іншої — правила формування цієї надмірності дуже складні і погано формалізовані для використання в сучасних програмно-апаратних комплексах. Тому для тривалого зберігання або передачі по низькошвидкісних лініях доцільно упаковувати текстові дані і забезпечувати їх простими засобами надмірності, наприклад CRC.


:: Реклама ::

 

:: Посилання ::


 

 

 


Copyright © Kivik, 2017