Коди з виявленням та виправленням помилок
Коли інформація постійно передається між різними частинами комп'ютера, зберігається у пристрої пам'яті, найімовірніше, отримана зрештою бітова комбінація відрізнятиметься від вихідної. Частинки бруду або жиру на магнітній поверхні, що записує, випадкова помилка в роботі електронної схеми - все це може викликати помилки при записі або читанні даних. Більше того, при використанні деяких технологій зберігання даних, фонове радіаційне випромінювання може змінювати бітові комбінації, записані в основній пам'яті машини.
Для вирішення цих проблем було розроблено багато технологій кодування даних, що дозволяють виявляти і навіть виправляти подібні помилки. В даний час ці технології широко використовуються при створенні внутрішніх компонентів комп'ютерів, тому вони є непомітними для користувачів, що працюють з машиною. Однак вони надзвичайно важливі, і це ще раз підкреслює значення результатів виконаних наукових досліджень. По суті, більшість роботи зі створення подібних технологій виконали математики-теоретики. Нижче розглянемо деякі з тих методів, які забезпечують надійність функціонування сучасних обчислювальних машин.
Код з контролем парності
Існує досить простий спосіб визначення помилок, побудований на тому принципі, що якщо кожна бітова комбінація, що обробляється, буде складатися з парної кількості одиниць, то виявлення комбінації з непарною кількістю одиниць буде свідчити про виникнення помилки.
Щоб використати цей принцип, необхідно створити систему, в якій будь-яка бітова комбінація міститиме парну кількість одиниць. Зазвичай це досягається шляхом додавання до вже існуючого коду додаткового біта [який називається бітомпарності або контрольним бітом], що найчастіше поміщається в старший кінець комбінації. В результаті восьмирозрядний код ASCII перетворюється на дев'ятирозрядний, а шістнадцятирозрядна бітова комбінація в двійковому додатковому коді стає сімнадцятирозрядною. У кожному випадку значення біта парності встановлюється рівним 0 або 1 виходячи з вимоги, щоб вся бітова комбінація в цілому містила непарне кількість одиниць. Наприклад, символ А в коді ASCII буде представлений як 101000000 [біт парності дорівнює 0], тоді як символ F у цьому ж коді матиме вигляд 001000111 [біт парності дорівнює 1]. Хоча вихідна восьмирозрядна комбінація, що представляє літеру А, містить парну кількість одиниць, а аналогічна комбінація, що представляє літеру F, - непарна кількість одиниць, обидва дев'ятирозрядні коди мають парну кількість одиниць. Якщо система буде побудована вказаним чином, то поява бітової комбінації з непарною кількістю одиниць свідчить про помилку і сигналізуватиме, що оброблені дані є невірними.
В даний час використання бітів парності є типовим рішенням для основної пам'яті машини. Хоча зовні складається враження, що комп'ютери використовують восьмирозрядні осередки пам'яті, насправді є дев'ятирозрядними, причому дев'ятий біт використовується як контрольний. Щоразу, як у пам'ять записується деяка восьмибітова комбінація, схема управління пам'яттю автоматично додає до неї необхідний контрольний біт щоб одержати дев'ятирозрядної комбінації. При зчитуванні інформації схема управління пам'яттю підраховує кількість одиниць отриманої комбінації. Якщо помилка не виявляється, контрольний біт видаляється та утворюється вихідна восьмирозрядна бітова комбінація. В іншому випадку схема управлінняпам'яттю повертає лічене восьмирозрядне значення із зазначенням, що воно спотворене і може відрізнятись від вихідного.
Довгі бітові комбінації часто доповнюються групою контрольних бітів, що утворюють контрольний байт. Кожен біт у цьому байті є контрольним і відноситься до певної групи бітів, розкиданих за основною бітовою комбінацією. Наприклад, один контрольний біт може відноситися до кожного восьмого біта, починаючи з першого, тоді як інший - до кожного восьмого біта, починаючи з другого, і т.д. В даному випадку легше виявити помилки, сконцентровані в одній області вихідної комбінації, оскільки їх наявність контролюватиметься групою контрольних бітів. Різні варіанти даного підходу до створення схем контролю називаються методом контрольних сум та методом використання коду циклічного контролю надмірності [CRC].
Коди з виправленням помилок
Незважаючи на те, що біт парності є ефективним методом виявлення помилок, він не дає інформації, необхідної для виправлення помилки, що виникла. Багатьох дивує сам факт, що можна розробити коди з виправленням помилок, що дозволяють не лише виявляти помилки, а й виправляти їх. Врешті-решт інтуїція підказує, що ми не в змозі виправити помилку в отриманому повідомленні, якщо заздалегідь не знаємо, про що там йдеться. Проте існує досить простий код, що дозволяє виправляти помилки, що виникають.
Для того щоб зрозуміти принцип дії цього коду, спочатку необхідно визначити дистанцію Хеммінга між двома кодовими комбінаціями, яка дорівнюватиме кількості бітів, що відрізняються в цих комбінаціях. Поняття дистанція Хеммінга отримало свою назву на честь Р.В. Хеммінгу [R.W. Hamming], який провів перші дослідження в галузі розробки кодів із виправленням помилок.Він звернувся до цієї проблеми у 1940-х роках через крайню ненадійність існуючих на той час релейних обчислювальних машин. Розглянемо наступний код:
A 000000 B 001111 C 010011 D 011100 E 100110 F 101001 G 110101 H 111010
Дистанція Хеммінгу між кодами букв А і В дорівнює чотирьом, а дистанція Хеммінгу між кодами букв В і С дорівнює трьом. Важливою особливістю цього коду є те, що дистанція Хеммінга між будь-якими двома комбінаціями буде не меншою за три. Якщо в результаті збою в якомусь окремому биті з'явиться помилкове значення, то помилка буде легко встановлена, оскільки комбінація, що вийшла, не є допустимим кодовим значенням. У будь-якій комбінації потрібно змінити не менше трьох бітів, перш ніж вона знову стане допустимою.
Якщо будь-якої комбінації виникла поодинока помилка, то легко можна обчислити її вихідне значення. Справа в тому, що дистанція Хеммінга для зміненої комбінації по відношенню до вихідної форми дорівнюватиме одиниці, тоді як по відношенню до інших дозволених комбінацій вона дорівнюватиме не менше ніж двом. При декодуванні деякого повідомлення досить просто порівнювати кожну отриману комбінацію бітів з допустимими комбінаціями коду, поки не буде знайдена комбінація, що знаходиться на дистанції, що дорівнює одиниці, від отриманої комбінації. Знайдена допустима кодова комбінація приймається за правильний символ, отриманий внаслідок декодування. Припустимо, що отримано бітову комбінацію 010100. Якщо порівняти її з допустимими бітовими комбінаціями коду, то буде отримано таблицю дистанцій:
A 2 B 4 C 3 D 1 E 3 F 5 G 2 H 4
За змістом цієї таблиці можна зробити висновок, що символ, що надійшов - це буква D, так як її бітова комбінація внайбільшою мірою відповідає отриманій.