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

Розділ 7

Основи теорії кодування

План викладення матеріалу

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

Дотатні умови однозначності декодування. Властивості розділових кодів.

Оптимальне кодування.

Коди, стійкі до перешкод. Коди Хемінга.

Задачі.

Комп 'ютерні проекти.

Література.

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

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

Не зменшуючи загальності, задачу кодування можна сформулю­вати так. Нехай заданий алфавіт А={а₁,..., а_r}, який складається зі скінченної кількості букв. Скінченну послідовність символів алфа­віту А: α = α _i1 α _i2 …α _il називають словам в алфавіті А, а число l - дов­жиною слова α. Довжину слова α позначаютьl(α).Множину всіх слів в алфавіті А позначають черезA*. Порожнє слово не містить жодної букви, його позначають , A *, l( )=0, A.

Якщо = _{1 2}, то ₁ називають початком, або префіксом слова , а ₁ – закінченням, або постфіксом слова . Якщо при цьому ₁≠ λ (відповідно, ₂≠ λ), то α ₁(відповідно, α ₂) називають власним початком (відповідно, власним значенням) слова α.

Нехай S – деяка підмножина множини A*, елементимножини S називають повідомленнями. Нехай також задано скінченний B ={b₁, …, b_q}. Через β позначмо слово в алфавіті B і через B* -- множинувсіхсліввалфавіті B. Задамовідображення F, яке кожному слову α, α S, ставить у відповідність слово β =F(α), β B*. Слово β називають кодом повідомленняα. Перехід від слова α до його коду називають кодуванням.

Якщо Ɩ BƖ =q, то кодування називають q-кодовим. Найбільш поширений випадок B={0, 1}– двійкове кодування. Саме цей випадок й розглядатимемо в подальшому, слово " двійкове" випускатимемо.

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

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

α ₁→ β ₁,

α ₂→ β ₂,

………..

α _r→ β _r,

де α ₁ϵ А, β ₁ B*, i=1, …, r. Схема σ задає відповідність між буквами алфавіту A і деякими словами алфавіту B. Вона визначає алфавітне кодування так: кожному слову = α _i1α _i2 … α _il з S ставиться у відповідність слово β = β _i1 β _i2 … β _il. Це слово β називають кодом слова . Слова β ₁, …, β _r (див. схему σ) називаютьелементарними кодами.

Рівномірнекодування. Рівномірнекодування зпараметрами k та n визнaчають так. Повідомлення α розбивають на блоки довжини k:

,

Де s≤ k (останній блок може бути коротшим, у такому разіспосібйогокодуванняспеціальнообумовлюється), x_i A, i =1, …, mk+s. Блоки довжини k розглядають як буквидеякогоалфавіту (таких блоків є, очевидно, r^k, оскількиалфавіт А складається з r букв) і кодують словами в алфавіті B однаковоїдовжиниn за схемою рівномірного кодування σ _{k, n}:

₁→ ₁

₂→ ₂

₃→ ₃

………

Надлишковістю схеми σ _{k, n} на символ повідомлення називають величину

Отже, ми описали два способи задання відображення F: S→ B*. Однозначне декодування є можливим, якщо існує обернене відображення F ^-1.