Основные понятия

Кодирование и декодирование

Шифрование и дешифровка являются частными случаями более общих понятий кодирования и декодирования.

Пусть $X$ и $Y$ — два произвольных множества. Будем называть пару отображений $c:X\rightarrow Y$ и $d:Y\rightarrow X$ кодированием и декодированием, если $d(c(x)) = x$ для всех $x\in X$.

Обычно, когда говорят о кодировании и декодировании, то считают множества $X$ и $Y$ не совсем произвольными: почти всегда эти множества — множества конечных последовательностей элементов каких-нибудь «алфавитов».

Поэтому далее мы будем считать, что $X$ состоит из конечных последовательностей элементов множества $A$, которое в дальнейшем мы будем называть словом «алфавит». А вот $Y$ мы будем считать множеством конечных последовательностей элементов двухэлементного множества $\{0, 1\}$.

Посимвольное кодирование

Будем говорить, что $c$ — посимвольное преобразование, если для любого $n$ и любой последовательности $x_1 x_2\ldots x_n$ выполнено

$$c(x_1 x_2 \ldots x_n) = c(x_1)c(x_2)\ldots c(x_n)$$

Если вдобавок ещё и существует преобразование $d$ такое, что $d(c(x))=x$ для всех $x\in X$, то будем называть $c$ посимвольным кодированием.

Есть хороший признак посимвольного кодирования, называемый префиксным свойством или условием Фано:

• для любых $x_1\ne x_2$ последовательность $c(x_1)$ не является началом последовательности $c(x_2)$

Посимвольное преобразование, обладающее префиксным свойством, является кодированием! Доказательство этого факта оставим читателю в качестве простого упражнения.