Русская Википедия:Алфавитное кодирование

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:К удалению Алфавитное кодирование — вид кодирования, построенный на взаимной однозначности кодирования слов некоторого алфавита при помощи замены каждой буквы некоторым словом того же или какого-либо другого алфавита[1]. Основоположником этого направления в России считается математик из Нижнего Новгорода Александр Александрович Марков[2]. При алфавитном кодировании количество элементарных кодов должно быть равно мощности алфавита сообщений, то есть должно быть фиксированным. В алфавитном кодировании преимущественно используются префиксные коды, так как свойство префикса гарантирует однозначную декодируемость[3].

Описание

Пусть существует некий алфавит (множество) <math>\alpha = \left\{ a_1, a_2, ..., a_r\right\}</math>, а также алфавит <math>\Beta= \left\{ b_1, b_2, ..., b_q\right\}</math>.

Слово в алфавите — упорядоченный набор элементов из алфавита вида: <math>A = \left\{ a_{i_1}, a_{i_2}, ..., a_{i_n}\right\}</math>

S(ℳ) — множество слов алфавита ℳ, S(β) — множество слов алфавита β

Суть алфавитного кодирования в том, что каждой букве алфавита ℳ сопоставляется слово из алфавита β согласно схеме кодирования Σ. <math>\Sigma \quad - \quad {\begin{matrix} a_1 \to B_1 \\ \\a_2 \to B_2 \\... \\a_r \to B_r \end{matrix}}</math>

Примечания

Шаблон:Примечания

Литература

  • Яблонский. Введение в дискретную математику ISBN 978-5-06-005943-4; 2008 г.
  • Марков А. А. Вопросы взаимной однозначности и сложности в алфавитном кодировании : Автореф. дис. … д-ра физ.-мат. наук. — М., 1983. — 17 с.
  • Марков А. А. Кодирование алфавитное // Математическая энциклопедия. — М.: Советская энциклопедия, 1979. — Т. 2. — С. 935—937.