Математическая энциклопедия - кодирование и декодирование

процесс представления информации в определенной стандартной форме и обратный процесс восстановления информации по ее такому представлению. В математич. литературе кодированием наз. отображение произвольного множества Ав множество конечных последовательностей (слов) в нек-ром алфавите В, а декодированием обратное отображение. Примерами кодирования являются: представление натуральных чисел в r-ичной системе счисления, при к-ром каждому числу N=i,2, ... ставится в соответствие слово b1b2 ... bl в алфавите В r={0, 1, ..., r-1} такое, что b1 неравно 0 и b1r^l-1+...+ bl-1r+bl=N; преобразование текстов на русском языке с помощью телеграфного кода в последовательности, составленные из посылок тока и пауз различной длительности; отображение, применяемое при написании цифр почтового индекса (см. рис.). В последнем случае каждой десятичной цифре соответствует слово в алфавите В 2={0, 1} длины 9, в котором символами 1 отмечены номера использованных линий (напр., цифре 5 соответствует слово 110010011). Исследование различных свойств К. и д. и построение эффективных в определенном смысле кодирований, обладающих требуемыми свойствами, составляет проблематику теории кодирования. Обычно критерий эффективности кодирования так или иначе связан с минимизацией длин кодовых слов (образов

элементов множества А), а требуемые свойства кодирования связаны с обеспечением заданного уровня помехоустойчивости, понимаемой в том или ином смысле. В частности, под помехоустойчивостью понимается возможность однозначного декодирования при отсутствии или допустимом уровне искажений в кодовых словах. Помимо помехоустойчивости, к кодированию может предъявляться ряд дополнительных требований. Напр., при выборе кодирования для цифр почтового индекса необходимо согласование с обычным способом написания цифр. В качестве дополнительных требований часто используются ограничения, связанные с допустимой сложностью схем, осуществляющих К. и д. Проблематика теории кодирования в основном создавалась под влиянием разработанной К. Шенноном (С. Shannon, [1]) теории передачи информации. Источником новых задач теории кодирования служат создание и совершенствование автоматизированных систем сбора, хранения, передачи и обработки информации. Методы решения задач теории кодирования главным образом комбинаторные, теоретико-вероятностные и алгебраические. Произвольное кодирование f множества (алфавита) Асловами в алфавите Вможно распространить на множество А* всех слов в А(сообщений) следующим образом:

где i=1, 2, . . ., k. Такое отображение f: наз. побуквенным кодированием сооб. щений. Более общий класс кодирований сообщений образуют автоматные кодирования, реализуемые инициальными асинхронными автоматами, выдающими в каждый момент времени нек-рое (быть может, пустое) слово в алфавите В. Содержательный смысл этого обобщения заключается в том, что автомат в разных состояниях реализует различные кодирования букв алфавита сообщений. Побуквенное кодирование это автоматное кодирование, реализуемое автоматом с одним состоянием: Одним из направлений теории кодирования является изучение общих свойств кодирования и построение алгоритмов распознавания этих свойств (см. Кодирование алфавитное). В частности, для побуквенных и автоматных кодирований найдены необходимые и достаточные условия для того, чтобы:

1) декодирование было однозначным, 2) существовал декодирующий автомат, т. е. автомат, реализующий декодирование с нек-рой ограниченной задержкой, 3) существовал самонастраивающийся декодирующий автомат (позволяющий в течение ограниченного промежутка времени устранить влияние сбоя во входной последовательности или в работе самого автомата).

Большинство задач теории кодирования сводится к изучению конечных или счетных множеств слов в алфавите В r. Такие множества наз. кодами. В частности, каждому однозначному кодированию f : (и побуквенному кодированию ) соответствует код Одно из основных утверждений теории кодирования состоит в том, что условие взаимной однозначности побуквенного кодирования накладывает следующее ограничение на длины li=l,if )кодовых слов f(i):

Справедливо и обратное утверждение: если (l0, ..., lm-1)набор натуральных чисел, удовлетворяющих (1), то существует взаимно однозначное побуквенное кодирование такое, что слово f(i)имеет длину li;. При этом, если числа li упорядочены по возрастанию, то в качестве f(i) можно взять первые после запятой li символов разложения числа в r-ичную дробь (метод Шеннона).

Наиболее законченные результаты в теории кодирования связаны с построением эффективных взаимно однозначных кодирований. Описанные здесь конструкции используются на практике для сжатия информации и выборки информации из памяти. Понятие эффективности кодирования зависит от выбора критерия стоимости. При определении стоимости L(f)взаимно однозначного побуквенного кодирования предполагается, что каждому числу поставлено в соответствие положительное число р i и Р={р 0, ..., Pm-1). Исследованы следующие варианты определения стоимости L(f):

причем предполагается, что в первых двух случаях р iвероятности, с к-рыми некоторый бернуллиевый источник порождает соответствующие буквы алфавита В т а в третьем случае р iзаданные длины кодовых слов. При первом определении стоимость равна средней длине кодового слова, при втором определении с ростом параметра tболее длинные кодовые слова оказывают все большее влияние на стоимость ( при и при ), при. третьем определении стоимость равна максимальному превышению длины li кодового слова над заданной длиной р i. Задача построения взаимно однозначного побуквенного кодирования f : В* т->В*r, минимизирующего стоимость L(f), равносильна задаче минимизации функции L(f) на наборах (l0, ..., 1 т-1 )из натуральных чисел, удовлетворяющих (1). Решение этой задачи известно при каждом из указанных определений стоимости. Пусть минимум величины L(f)на наборах (l0, . . ., lm-1 )из произвольных (не обязательно натуральных) чисел равен Lr(P)и достигается на наборе (l0 (Р), ...,l т-1 (Р)). Неотрицательная величина I(f) = L(f) Lr(P)наз. избыточностью, а величина I(f)/L(f)относительной избыточностью кодирования f. Для избыточности взаимно однозначного кодирования построенного по методу Шеннона для длин справедливо неравенство I(f)<1. При первом, наиболее употребительном, определении стоимости как среднего числа кодовых символов, приходящихся на одну букву порождаемого источником сообщения, величина Lr(P)равна энтропии Шеннона

источника, вычисленной по основанию r, a li(P)=-logrpi. Граница избыточности I(f) = L ср(f)- Н r(P)<1 может быть улучшена с помощью так наз. кодирования блоками длины k, при к-ром сообщения длины k(а не отдельные буквы) кодируются по методу Шеннона. Избыточность такого кодирования не превышает 1/k. Этот же прием используется для эффективного кодирования зависимых источников. В связи с тем, что определение длин li при кодировании по методу Шеннона основано на знании статистики источника, для нек-рых классов источников разработаны методы построения универсального кодирования, гарантирующего определенную верхнюю границу избыточности для любого источника из этого класса. В частности, построено кодирование блоками длины к, избыточность к-рого для любого бернуллиевого источника асимптотически не превышает (при фиксированных ), причем эта асимптотическая граница не может быть улучшена.

продолжение Кодирование и декодорование...

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

При исследовании задач построения эффективных помехоустойчивых кодирований обычно рассматривают кодирования к-рым соответствуют коды {f(0), . .., f(m-1)}, принадлежащие множеству слов длины пв алфавите В r, и предполагают, чтo буквы алфавита сообщений В т равновероятны. Эффективность такого кодирования оценивают избыточностью I(f)= п-logrm или скоростью передачи В(f)= При определении помехоустойчивости кодирования формализуется понятие ошибки и вводится в рассмотрение нек-рая модель образования ошибок. Ошибкой типа замещения (или просто ошибкой) наз. преобразование слова, состоящее в замещении одного из его символов другим символом алфавита В r. Напр., проведение лишней линии при написании цифры почтового индекса приводит к замещению в кодовом слове символа 0 символом 1, а отсутствие нужной линии к замещению символа 1 символом 0. Возможность обнаружения и исправления ошибок основана на том, что для кодирования f, обладающего ненулевой избыточностью, декодирование f^-1 может быть произвольным образом доопределено на r ^п -тсловах из не являющихся кодовыми. В частности, если множество разбито на тнепересекающихся подмножеств D0, . .., Dm-1 таких, что а декодирование f^-1 доопределено так, что f^-1(Di)=i, то при декодировании будут исправлены все ошибки, преобразующие кодовое слово f(i) в Di, i=0, ..., т-1. Аналогичная возможность имеется и в случае ошибок других типов таких, как стирание символа (замещение символом другого алфавита), изменение числового значения кодового слова на b=1, ..., r-1, i=0, 1, ... (арифметическая ошибка), выпадение или вставка символа и т. п.

В теории передачи информации (см. Информации передача )рассматриваются вероятностные модели образования ошибок, называемые каналами. Простейший канал без памяти задается вероятностями р ij замещения символа iсимволом j. Для канала определяется величина (пропускная способность)