КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

где максимум берется по всем наборам (q₀, . . ., q_m-1 )таким, что и Эффективность кодирования f характеризуется скоростью передачи R(f), а помехоустойчивость - средней вероятностью ошибки декодирования Р(f) (при наилучшем разбиении. В ⁿ_r на подмножества D_i). Основной результат теории передачи информации (теорема Шеннона) состоит в том, что пропускная способность Сявляется верхней гранью чисел Rтаких, что для любого е>0 при всех п, начиная с нек-рого, существует кодирование

для к-рого и Р(f)<e.

Другая модель образования ошибок (см. Код с исправлением ошибок, Код с исправлением арифметических ошибок, Код с исправлением выпадений и вставок )характеризуется тем, что в каждом слове длины ппроисходит не более заданного числа tошибок. Пусть E_i(t)- множество слов, получаемых из f(i)в результате tили менее ошибок. Если для кода

множества E_i(t), i=0, ..., m-1, попарно не пересекаются, то при декодировании таком, что E_i(t)Н D_i, будут исправлены все ошибки, допустимые рассматриваемой моделью образования ошибок, и такой код наз. кодом с исправлением tошибок. Для многих типов ошибок (напр., замещений, арифметич. ошибок, выпадений и вставок) функция d( х, у), равная минимальному числу ошибок данного типа, преобразующих слово в слово является метрикой, а множества E_i(t)- метрическими шарами радиуса t. Поэтому задача построения наиболее эффективного (т. е. максимального по числу слов т)кода в В ⁿ_r с исправлением tошибок равносильна задаче плотнейшей упаковки метрического пространства шарами радиуса t. Код для цифр почтового индекса не является кодом с исправлением одной ошибки, так как d(f(0), f(8))=1 и d(f(5), f(8)) = 2, хотя все другие расстояния между кодовыми словами не менее 3.

Задача исследования величины I_r(n, t)- минимальной избыточности кода в с исправлением tошибок типа замещения распадается на два основных случая. В первом случае, когда tфиксировано, а справедлива асимптотика

причем достигается "мощностная" граница, основанная на подсчете числа слов длины пв шаре радиуса t. Асимптотика величины I_r(n, t )при г>2, а также при r=2 для многих других типов ошибок (напр., арифметич. ошибок, выпадений и вставок) не известна (1978). Во втором случае, когда t=[pn], где р - некоторое фиксированное число, 0<р<(r-1)/2r, а "мощностная" граница

где T_r(p)=-p log_r(p/(r- 1))-(1-р)log_r(l- p), существенно улучшена. Имеется предположение, что верхняя граница

полученная методом случайного выбора кода, является асимптотически точной, т. е. I_r( п,[ рп])~пТ _r(2р). Доказательство или опровержение этого предположения - одна из центральных задач теории кодирования.

Большинство конструкций помехоустойчивых кодов являются эффективными, когда длина пкода достаточно велика. В связи с этим особое значение приобретают вопросы, связанные со сложностью устройств, осуществляющих кодирование и декодирование (кодера и декодера). Ограничения на допустимый тип декодера или его сложность могут приводить к увеличению избыточности, необходимой для обеспечения заданной помехоустойчивости. Напр., минимальная избыточность кода в В ⁿ₂, для к-рого существует декодер, состоящий из регистра сдвига и одного мажоритарного элемента и исправляющий одну ошибку, имеет порядок (ср. с (2)). В качестве математич. модели кодера и декодера обычно рассматривают схемы из функциональных элементов и под сложностью понимают число элементов в схеме. Для известных классов кодов с исправлением ошибок проведено исследование возможных алгоритмов К. и д. и получены верхние границы сложности кодера и декодера. Найдены также нек-рые соотношения между скоростью передачи кодирования, помехоустойчивостью кодирования и сложностью декодера (см. [5]).

Еще одно направление исследований в теории кодирования связано с тем, что многие результаты (напр., теорема Шеннона и граница (3)) не являются "конструктивными", а представляют собой теоремы существования бесконечных последовательностей {К _п} кодов В связи с этим предпринимаются усилия, чтобы доказать эти результаты в классе таких последовательностей {К _п} кодов, для к-рых существует машина Тьюринга, распознающая принадлежность произвольного слова длины lмножеству за время, имеющее медленный порядок роста относительно l(напр., llog l).

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

Лит.:[1] Шеннон К., Работы по теории информации и кибернетике, пер. с англ., М., 1963; [2] Берлекэмп Э., Алгебраическая теория кодирования, пер. с англ., М., 1971; [3] Питерсон У., Уэлдон Э., Коды, исправляющие ошибки, пер. с англ., 2 изд., М., 1976; [4] Дискретная математика и математические вопросы кибернетики, т.1, М., 1974, раздел 5; [5] Бассалыго Л. А., Зяблов В. В., Пинскер М. С, "Пробл. передачи информации", 1977, т. 13, № 3, с. 5-17; [В] Сидельников В. М., "Матем. сб.", 1974, т. 95, в. 1, с. 148 - 58.

В. И. Левенштейн.