Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

Код



План:


Введення

Ця стаття - про код в теорії інформації, інші значення цього слова див код (значення).

Код - правило ( алгоритм) зіставлення кожному конкретному повідомленням строго певної комбінації символів ( знаків) (або сигналів). Кодом також називається окрема комбінація таких символів (знаків) - слово. Для відмінності цих термінів, код в останньому значенні ще називається кодовим словом.


1. Кодування

Процес перетворення повідомлення в комбінацію символів відповідно до кодом називається кодуванням, процес відновлення повідомлення з комбінації символів називається декодуванням.

2. Кодові дерева

Для наочного опису кодів використовуються кодові дерева. Якщо число вузлів на кожному його рівні містить m_2 ^ l вузлів, де l - номер рівня (корінь дерева знаходиться на нульовому рівні), воно називається повним. Очевидно, величина m_2 ^ {l_ {max}} , Звана об'ємом дерева, характеризує максимальне число кодових комбінацій, яке можна построть за допомогою даного дерева.

У теорії побудови трансляторів, таке дерево описує безліч всіх можливих ланцюжків-висновків з формальної граматики.


3. Префіксний код

Префіксним називається код, який не має жодного кодового слова, яке було б префіксом (початком) будь-якого іншого кодового слова даного коду. Будь префіксний код є разделімие (тобто будь-яку послідовність кодових слів завжди можна однозначно розділити на окремі з них). [1] Прикладами префіксних кодів є коди Шеннона, Шеннона-Фано і Хаффмана.

4. Приклади

Рівномірний кодування: для алфавіту з m 1 символ використовуються кодові слова з довжиною n = up (log_ {m_2} m_1) , Де up - округлення до більшого цілого. У цьому випадку невикористаними залишаються log_ {m_2} m_1-n кодових слів, а іншим проставляються у відповідність символи первинного алфавіту. Код Бодо має фіксовану довжину 5 символів.

Префіксние коди: Код Шеннона-Фано - перший алгоритм нерівномірного кодування. Код Хаффмана - відомий метод побудови оптимального нерівномірного коду (ОНК) з використанням дерев. Арифметичне кодування - узагальнення коду Хаффмана.


Література

Цимбал В. П. Теорія інформації та кодування. - К.: Вища Школа, 1977. - 288 с.

Примітки

  1. Габідулін, Е. М., Пилипчук, Н. І. 3.3. Префіксний код. / / Лекції з теорії інформації - М .: МФТІ, 2007. - С. 43-49. - 214 с. - ISBN 5-7417-0197-3.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
QR-код
Код INSEE
Код Грея
Код ІАТА
Штриховий код
ZIP-код
Код (значення)
Лінійний код
© Усі права захищені
написати до нас