131

Дискретна Математика :: Теорія кодування

Розділ VI. Теорія кодування

Питання кодування здавна відігравало значну роль у математиці. Наприклад, десяткова позиційна система числення – це спосіб кодування натуральних чисел. Римські цифри – інший спосіб кодування натуральних чисел, до того ж більш наглядний та природній: палець – І, п’ятірня – V, дві п’ятірні – Х. Але при цьому способі кодування складніше виконувати арифметичні дії над великими числами, тому він був витиснений позиційною десятковою системою.

Раніше засоби кодування відігравали допоміжну роль і не розглядались як окремий предмет математичного вивчення, але з появою комп’ютерів ситуація радикально змінилась. Теорія кодування виникла у 40-х роках XX століття після появи робіт К. Шенона. У цій теорії досліджуються методи кодування, пов’язані з основними математичними моделями, які відображають істотні риси реальних інформаційних систем.

Кодування буквально пронизує інформаційні технології і є центральним питанням при розв’язанні самих різних (практично усіх задач) програмування:

• представлення даних довільної природи (наприклад, чисел, тексту, графіки) у пам’яті комп’ютера;

• захист інформації від несанкціонованого доступу;

• забезпечення перешкодозахищеності при передачі даних по каналам зв’язку;

• стиснення інформації у базах даних.

Властивості, які вимагаються від кодування, бувають різної природи:

• існування декодування – це дуже природна властивість, але навіть вона потрібна не завжди. Наприклад, трансляція програми на мові високого рівня у машинні команди – це кодування, для якого не потрібно однозначного декодування;

• перешкодозахищеність, або виправлення помилок – коли від кодування вимагається можливість відновлення інформації в разі її пошкодження;

• задана складність (або простота) кодування та декодування. Наприклад, у криптографії вивчаються такі способи кодування, при яких є просто обчислювальна функція F, але визначення зворотної функції F^-1 потребує дуже складних обчислень.

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

Тема 21. Теорія кодування

21.1. Алфавітне й рівномірне кодування

Без утрати загальності можна сформулювати задачу кодування так.

Означення 21.1. Нехай задано алфавіт А = {a₁, …, a_n} зі скінченної кількості символів, які називають буквами. Скінченну послідовність букв алфавіту A називають словом у цьому алфавіті. Для позначення слів будемо використовувати малі грецькі літери: = a_i1a_i2…a_il. Число l – кількість букв у слові  - називають довжиною слова  і позначають l() або ||.

Множину всіх слів у алфавіті A позначають як A*. Порожнє слово позначають ; зазначимо, що A, A*, ||=0.

Означення 21.2. Якщо слово  має вигляд  = ₁₂, то ₁ називають початком або префіксом слова , а ₂ – його закінченням або постфіксом. Якщо при цьому ₁ (відповідно, ₂), то ₁ називають власним початком (відповідно власним закінченням) слова .

Для слів визначена операція конкатенації або зчеплення.

Означення 21.3. Конкатенація слів  та  є слово , отримане виписуванням підряд спочатку всіх букв слова , а потім всіх букв слова . Зазвичай операція зчеплення ніяк не позначається.

Означення 21.4. Довільна множинаL слів у деякому алфавіті A називається мовою в цьому алфавіті, LA*.

Нехай задано алфавіти A = {a₁, …, a_n}, B = {b₁, …, b_m} і функція F: S  B*, де S – деяка множина слів у алфавіті A, S  A*. Тоді функція F називається кодуванням, елементи множини S – повідомленнями, а елементи  = F(), S, B* – кодами (відповідних повідомлень). Обернена функція F^-1, якщо вона існує, називається декодуванням.

Якщо |B| = m, то F називають m-ковим кодуванням. Найчастіше використовується алфавіт B = {0, 1}, тобто двійкове кодування. Саме його ми й розглядатимемо в наступних підрозділах, випускаючи слово «двійкове».

Відображення F задають якимось алгоритмом. Є два способи задати відображення F.

Алфавітне кодування задають схемою (або таблицею кодів) :

a₁  ₁,

a₂  ₂,

…

a_n  _n,

де a_i  A, _I  B*, i = 1,…,n. Схема  задає відповідність між буквами алфавіту A та деякими словами в алфавіті B. Вона визначає алфавітне кодування так: кожному слову  = a_i1a_i2…a_il із повідомлення S поставлено у відповідність слово  = _i1_i2…_il – його код. Слова ₁, …, _n називають елементарними кодами.

Наприклад, розглянемо алфавіт A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, B = {0, 1} і схему:

₁ = 00, 11, 210, 311, 4100, 5101, 6110, 7111, 81000, 91001.

Ця схема однозначна, але кодування не є взаємно однозначним:

F_1 (333) = 111111 =F_ (77),

а значить, неможливе декодування. З іншого боку, схема

₁ = 00000, 10001, 20010, 30011, 40100, 50101,

6 0110, 70111, 81000, 91001,

відома під назвою «двійково-десяткове кодування», допускає однозначне декодування.

Рівномірне кодування з параметрами k й r задають так. Повідомлення  розбивають на блоки довжиною k:

 = (x₁…x_k)(x_k+1…x_2k)…(x_mk+1…x_pk+s),

де sk (останній блок може бути коротшим, у такому разі спосіб його кодування спеціально обумовлюють), x_iA, i = 1,…, pk + s. Блоки довжиною k розглядають як «букви» якогось алфавіту (таких блоків, очевидно, n^k, бо алфавіт A складається з n букв) і кодують словами в алфавіті B довжиною r за схемою рівномірного кодування _k,r:

₁  ₁,

₂  ₂,

…

.

Надлишковістю схеми _k,r на символ повідомлення називають величину .