Код

У этого термина существуют и другие значения, см. Код (значения).

Код в правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков) (или сигналов). Кодом также называется отдельная комбинация таких символов (знаков) в слово. Для различия этих терминов, код в последнем значении ещё называется кодовым словом.

[править] Кодирование

Основная статья: Кодирование

Процесс преобразования сообщения в комбинацию символов в соответствии с кодом называется кодированием, процесс восстановления сообщения из комбинации символов называется декодированием.

[править] Кодовые деревья

Для наглядного описания кодов используются кодовые деревья. Если число узлов на каждом его уровне содержит $m_2^l$ узлов, где l в номер уровня (корень дерева находится на нулевом уровне), оно называется полным. Очевидно, величина $m_2^{l_{max}}$ , называемая объёмом дерева, характеризует максимальное число кодовых комбинаций, которое можно построить при помощи данного дерева.

В теории построения трансляторов, такое дерево описывает множество всех возможных цепочек-выводов из формальной грамматики.

[править] Префиксный код

Основная статья: Префиксный код

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

[править] Примеры

Равномерное кодирование: для алфавита с m₁ символами используются кодовые слова с длиной $n=up(log_{m_2}m_1)$ , где up в округление до большего целого. В этом случае неиспользованными остаются $log_{m_2}m_1-n$ кодовых слов, а остальным проставляются в соответствие символы первичного алфавита. Код Бодо имеет фиксированную длину 5 символов.

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

[править] Литература

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

[править] См. также

[править] Примечания

в‘ Габидулин, Э. М., Пилипчук, Н. И. 3.3. Префиксный код. // Лекции по теории информации. в М.: МФТИ, 2007. в С. 43в49. в 214 с. в ISBN 5-7417-0197-3

[0] в‘ Габидулин, Э. М., Пилипчук, Н. И. 3.3. Префиксный код. // Лекции по теории информации. в М.: МФТИ, 2007. в С. 43в49. в 214 с. в ISBN 5-7417-0197-3

[1]

Код

Содержание

[править] Кодирование

[править] Кодовые деревья

[править] Префиксный код

[править] Примеры

[править] Литература

[править] См. также

[править] Примечания

Личные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Участие

Печать/экспорт

Инструменты

На других языках