Алфавитное кодирование

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

Описание

Пусть существует некий алфавит (множество) $\alpha =\{a_1,a_2,...,a_r\}$, а также алфавит $\mathrm{B}=\{b_1,b_2,...,b_q\}$.

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

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

Суть алфавитного кодирования в том, что каждой букве алфавита ℳ сопоставляется слово из алфавита β согласно схеме кодирования Σ. $\mathrm{\Sigma }-\begin{array}{c}{a}_1\to B_1\\ \\ a_2\to B_2\\ ...\\ a_r\to B_r\end{array}$

Литература

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