Код

Код — взаимно-однозначное отображение конечного упорядоченного множества символов, принадлежащих некоторому конечному алфавиту, на иное, не обязательно упорядоченное, как правило более обширное множество символов для кодирования передачи, хранения или преобразования информации[источник не указан 2137 дней].

Кодирование — преобразование данных путём установления однозначного смысла между элементами[1], не принадлежащими к единому алфавиту, с одинаковыми порядковыми номерами. Для примера, код Морзе: в нём любому символу будет соответствовать одна последовательность из точек и тире. Двоичный код: комбинации его нулей и единиц тоже имеют порядок.

Последовательность элементарных закодированных символов принято называть кодовым сообщением, или кодовой посылкой. Иногда последовательность закодированных символов известной длины называют кодовым словом, или кодовым кадром.

КодированиеПравить

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

Кодовые деревьяПравить

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

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

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

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

ПримерыПравить

Равномерное кодирование: для алфавита с m1 символами используются кодовые слова с длиной  , где up — округление до большего целого. В этом случае неиспользованными остаются   кодовых слов, а остальным проставляются в соответствие символы первичного алфавита. Код Бодо имеет фиксированную длину 5 символов.

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

См. такжеПравить

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

  1. Такими элементами выступают уникальные символы, или отличные друг от друга обозначения, в контексте данного алфавита.
  2. Габидулин Э. М., Пилипчук Н. И. Лекции по теории информацииМФТИ, 2007. — С. 43—49. — 214 с. — ISBN 978-5-7417-0197-3

ЛитератураПравить

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