Спирина, М.С. Дискретная математика

6.4. Обработка сообщений как кодирование Ты должен идти не той дорогой, какой идут другие, но той, которой следует идти. Сенека Основные понятия теории кодирования. Пусть заданы два ал ­ фавита А и В, состоящие из конечного числа символов: А = {аь а2, ..., йдг } и В - {йь Ь2, ..., Ъ м}. Кортеж в алфавите А назовем словом а = ah а2, ..., а„ ..., ап, где / е [1, л], число п показывает длину слова а и обозначается п = 1(a). Пустое слово обозначается Л: 1(A) = |Л| = 0. Для слова а = а 1;..., а 2 буква а! называется началом, или префиксом, слова а , а буква а2 — окончанием, или постфиксом, слова а. Слова, как и кортежи вообще, можно соединять. Для этого префикс второго слова дол­ жен следовать сразу за постфиксом первого, при этом в новом сло­ ве они, естественно, утрачивают свой статус, если только одно из слов не было пустым. Соединение слов а! и а 2 обозначается а , а 2, соединение п одинаковых слов а обозначается а", причем а 0= Л. Множество всех непустых слов алфавита А обозначим А*: А* = = {а | / (сх) > 0}. Множество А называют алфавитом сообщений, а множество В — кодирующим алфавитом. Множество слов, состав­ ленных в алфавите В, обозначим В*. Обозначим через F отображение слов алфавита А в алфавит В. Тогда слово Р = /Да) назовем кодом слова а (от лат. codex). Кодиро­ ванием называют универсальный способ отображения информа­ ции при ее хранении, передаче и обработке в виде системы соот­ ветствий между элементами сообщений и сигналами, при помо­ щи которых эти элементы можно зафиксировать. Таким образом, код — правило однозначного преобразования (т.е. функция) со ­ общения из одной символической формы представления (исход­ ного алфавита А) в другую (объектный алфавит В), обычно без каких-либо потерь информации. Процесс преобразования F: А* —» —> В* слов исходного алфавита А в алфавит В называется кодиро­ ванием информации. Процесс обратного преобразования слова р е В* в слово а е А* называется декодированием. Очевидно, для этого должно быть р е F(A). Таким образом, деко­ дирование — функция, обрат­ ная /^(рис. 6.4). Правила обработки сообще­ ний могут быть различными: поэлементное кодирование, с помощью алгоритма, кодиро­ вание с помощью различных Рис. 6.4. Схема декодирования 309