Коды

Формальное определение link

В теории информации и теории кодирования кодом называют правило (или отображение), которое преобразует каждый символ (или последовательность символов) из некоторого исходного алфавита в конечную последовательность символов над алфавитом кода (как правило, это биты $0$ и $1$).

• Исходный алфавит $\Sigma$: множество элементов, которые мы хотим представить (например, буквы, слова, значения пикселей).

• Кодовый алфавит $S$: множество символов, которыми мы фактически представляем информацию (обычно ${0,1}$).

• Множество кодовых слов — это подмножество $S^*$, содержащее кодовое слово, назначенное каждому символу исходного алфавита.

Формально, код — это инъективная функция

$$ f: \Sigma \longrightarrow S^*, $$

которая каждому символу $\sigma \in \Sigma$ сопоставляет уникальное кодовое слово $f(\sigma)\in S^*$.

Неформальное определение link

На практике мы часто отождествляем код с его образом, множеством кодовых слов $$ C = f(\Sigma) = \lbrace f(\sigma)\mid \sigma \in \Sigma \rbrace \subseteq S^* $$

Таким образом, когда пишут $``\text{код } C \text{ над алфавитом } S’’$, подразумевают $``\text{множество } C \text{ строк, составленных из символов } S’’$, а за этим стоит неявная функция $f$, чьи выходные значения образуют именно это множество строк.