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

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

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

Пусть \(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)\)

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