алфавітний кодування

У загальному випадку завдання кодування можна представити таким чином. Нехай задані два алфавіту А і В, що складаються з кінцевого числа символів:

Елементи алфавіту називаються буквами. Упорядкований набір в алфавіті А назвемо словом

де. число п показує кількість букв в слові і називається довжиною слова. позначається п = l () = | |.

Пусте слово позначається:

буква a1, називається початком, або префіксом, слова. а буква an - закінченням, або постфіксом, слова.

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

З'єднання слів і позначається. з'єднання п однакових слів позначається. причому.

Безліч всіх непустих слів алфавіту А позначимо А *:

Безліч А називають алфавітом повідомлень, а безліч В - кодований алфавітом. Безліч слів, складених в алфавіті В, позначимо В *.

Позначимо через F відображення слів алфавіту А в алфавіт В. Тоді слово назвемо кодом слова.

Кодуванням називають універсальний спосіб відображення інформації при її зберіганні, передачі і обробці у вигляді системи відповідностей між елементами повідомлень і сигналами, за допомогою яких ці елементи можна зафіксувати. Таким чином, код - правило однозначного перетворення (тобто функція) повідомлення з однієї символічної форми подання (вихідного алфавіту А) в іншу (об'єктний алфавіт В), зазвичай без будь-яких втрат інформації. Процес перетворення F: А * → В * слів вихідного алфавіту А в алфавіт Вназивается кодуванням інформації.

Процес зворотного перетворення слова в слово називається декодуванням. Таким чином, декодування - функція, зворотна F, тобто F-1.

Так як для будь-якого кодування повинна виконуватися операція декодування, то відображення має бути оборотним (біекція).

Якщо | B | = m, то F називається m-ічним кодуванням, найбільш поширений випадок В = - двійкове кодування. Саме цей випадок і розглядається в подальшому.

Якщо все кодові слова мають однакову довжину, то код на-ни опиняються рівномірним, або блоковим.

Алфавітний (або побуквенное), кодування можна задати таблицею кодів. Кодом або кодує функцією, буде служити деяка підстановка. тоді

Таке побуквенное кодування позначається. Безліч кодів букв називається безліччю елементарних кодів. Алфавітний ко-дирования можна використовувати для будь-якого безлічі повідомлень. Таким чином, алфавітний кодування є найпростішим, і його завжди можна ввести на непустих алфавітах.

Нехай задані алфавіти

Тоді таблиця кодування може бути підстановкою:

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

не є взаємно-однозначної. Наприклад, набір з шести одиниць 111111 може відповідати як слову 333, так і 77, а також 111111, 137, 3311 або 7111 плюс будь-яка перестановка.

Схема алфавітного кодування називається префиксной, якщо елементарний код однієї літери не є префіксом елементарного коду іншої літери.

Схема алфавітного кодування називається разделімого, якщо будь-яке слово, складений-ве з елементарних кодів, розкладається на елементарні коди єдиним чином.

Алфавітний кодування з разделімого схемою допускає де-кодування. Можна довести, що префиксная схема є роздільна.

Для того щоб схема алфавітного кодування була разделімого, необхідно, щоб довжини елементарних кодів задовольняли співвідношенню, відомому як нерівність Макміллана.