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

Процесс представления информации в определенной стандартной форме и обратный процесс восстановления информации по ее такому представлению. В математич. литературе кодированием наз. отображение произвольного множества Ав множество конечных последовательностей (слов) в нек-ром алфавите В, а декодированием — обратное отображение. Примерами кодирования являются: представление натуральных чисел в r-ичной системе счисления, при к-ром каждому числу N=i,2, ... ставится в соответствие слово b1b2 ... bl в алфавите В такое, что b1 неравно 0 и b1rl-1+...+ bl-1r+bl=N; преобразование текстов на русском языке с помощью телеграфного кода в последовательности, составленные из посылок тока и пауз различной длительности; отображение, применяемое при написании цифр почтового индекса (см. рис.). В последнем случае каждой десятичной цифре соответствует слово в алфавите В длины 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 и , принадлежащие множеству слов длины пв алфавите В 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. Для канала определяется величина (пропускная способность) где максимум берется по всем наборам (q0, . . ., qm-1 )таким, что и Эффективность кодирования f характеризуется скоростью передачи R(f), а помехоустойчивость — средней вероятностью ошибки декодирования Р(f) (при наилучшем разбиении. В nr на подмножества Di). Основной результат теории передачи информации (теорема Шеннона) состоит в том, что пропускная способность Сявляется верхней гранью чисел Rтаких, что для любого е>0 при всех п, начиная с нек-рого, существует кодирование для к-рого и Р(f)<e. Другая модель образования ошибок (см. Код с исправлением ошибок, Код с исправлением арифметических ошибок, Код с исправлением выпадений и вставок )характеризуется тем, что в каждом слове длины ппроисходит не более заданного числа tошибок. Пусть Ei(t)- множество слов, получаемых из f(i)в результате tили менее ошибок. Если для кода множества Ei(t), i=0, ..., m-1, попарно не пересекаются, то при декодировании таком, что Ei(t)Н Di, будут исправлены все ошибки, допустимые рассматриваемой моделью образования ошибок, и такой код наз. кодом с исправлением tошибок. Для многих типов ошибок (напр., замещений, арифметич. ошибок, выпадений и вставок) функция d( х, у), равная минимальному числу ошибок данного типа, преобразующих слово в слово является метрикой, а множества Ei(t)- метрическими шарами радиуса t. Поэтому задача построения наиболее эффективного (т. е. максимального по числу слов т)кода в В nr с исправлением tошибок равносильна задаче плотнейшей упаковки метрического пространства шарами радиуса t. Код для цифр почтового индекса не является кодом с исправлением одной ошибки, так как d(f(0), f(8))=1 и d(f(5), f(8)) = 2, хотя все другие расстояния между кодовыми словами не менее 3. Задача исследования величины Ir(n, t)- минимальной избыточности кода в с исправлением tошибок типа замещения распадается на два основных случая. В первом случае, когда tфиксировано, а справедлива асимптотика причем достигается "мощностная" граница, основанная на подсчете числа слов длины пв шаре радиуса t. Асимптотика величины Ir(n, t )при г>2, а также при r=2 для многих других типов ошибок (напр., арифметич. ошибок, выпадений и вставок) не известна (1978). Во втором случае, когда t=[pn], где р — некоторое фиксированное число, 0<р<(r-1)/2r, а "мощностная" граница где Tr(p)=-p logr(p/(r- 1))-(1-р)logr(l- p), существенно улучшена. Имеется предположение, что верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir( п,[ рп])~пТ r(2р). Доказательство или опровержение этого предположения — одна из центральных задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длина пкода достаточно велика. В связи с этим особое значение приобретают вопросы, связанные со сложностью устройств, осуществляющих кодирование и декодирование (кодера и декодера). Ограничения на допустимый тип декодера или его сложность могут приводить к увеличению избыточности, необходимой для обеспечения заданной помехоустойчивости. Напр., минимальная избыточность кода в В n2, для к-рого существует декодер, состоящий из регистра сдвига и одного мажоритарного элемента и исправляющий одну ошибку, имеет порядок (ср. с (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. В. И. Левенштейн.