Коди

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

Загальна схема процесу передачі та прийому інформації має такій вигляд:

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

Наприклад, якщо хочемо передати слово 00101, то повторюючи кожен символ тричі, кодуємо його у слово 000000111000111, яке й відправляємо в канал зв’язку. Припустимо, на виході з каналу зв’язку ми одержали 010000110000111. Розбираємо одержане слово на групи по три символи: 010    . далі кожну групу символів замінюємо тим символом, який найчастішє у цій групі трапляється. Одержуємо початкове слово 00101.

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

Економніший з цього погляду клас кодів становлять так звані коди з перевіркою на парність. Найпростіший код з перевіркою на парність полягає в тому, що ми дописуємо до послідовності з нулів та одиниць, яку збираємося пропустити через канал зв’язку, ще один символ (0 або 1) так, щоб загальна кількість одиниць стала парною. Наприклад до слова 00101 дописуємо 0, а до слова10101 дописуємо 1. одержуємо довші слова 001010 та 101011, які передаємо. На виході з каналу зв’язку спочатку підраховують парність кількості входжень одиниць в одержаному слові. Якщо ця кількість парна, то роблять висновок, що помилки при передачі не з’явилося, а процес декодування полягає просто у закресленні останнього символу в одержаному слові. Якщо ж кількість одиниць в одержаному слові виявилась непарною, то можна лише зробити висновок, що при передачі з’явились помилки, але не можна відновити передане слово. Кажуть, що такий код виявляє помилки, тоді як розглянутий вище код з повтореннями не лише їх виявляє, а й виправляє.

Розглянуті два приклади кодів дуже елементарні, тому кожен з них має серйозні недоліки. Предмет теорії кодування полягає у створенні досконаліших кодів, які б об’єднували переваги і не мали недоліків щойно розглянутих кодів. Значною мірою побудова такbх кодів ґрунтується на поєднанні двох основних прийомів: повторення символів та перевірки на парність.

Ми ознайомимося з важливим класом так званими лінійними кодами. Для лінійних кодів кодовими словами є елементи скінченновимірних лінійних просторів над скінченним полем. Тому ми починаємо з основних факторів пр скінченні поля.