Информации Передача

Составная часть информации теории, относящаяся к изучению процесса переноса информации от источника сообщений к получателю сообщений (адресату). В теории И. п. изучаются оптимальные и близкие к оптимальным методы И. п. по каналам связи в предположении, что можно в широких пределах варьировать методы кодирования сообщений в сигналы на входе канала и декодирования сигналов на выходе канала в сообщения на выходе (см. Кодирование и декодирование). Общую схему системы И. п., впервые рассмотренную К. Шенноном (С. Shannon, [1]), можно описать следующим образом. Источник сообщений вырабатывает сообщения, подлежащие передаче по каналу связи от источника к получателю. Обычно предполагают, что это сообщение — случайная величина x, определенная на нек-ром вероятностном пространстве(W, U, Р), принимающая значения в нек-ром измеримом пространстве и имеющая распределение вероятностей р(-). Часто где D — множество значений параметра t, является случайным процессом с дискретным или непрерывным временем со значениями в нек-ром измеримом пространстве (X, SX )-Напр., в случае дискретного времени x= или случайные величины xk, принимающие значения в измеримом пространстве (X, SX), наз. компонентами сообщения на входе и часто трактуются как сообщения, вырабатываемые источником в моменты времени k. Наборы x п= (x1, ..., x п), принимающие значения в пространстве ( Х п, SXn), т. е. в n-кратном произведении пространств (X, SX), паз. отрезками сообщений длины пна входе. Аналогичным образом определяются соответствующие понятия и в случае, когда сообщение — случайный процесс с непрерывным временем. Сообщение на выходе, получаемое адресатом,- это тоже случайная величина определенная на том же вероятностном пространстве и принимающая значения в измеримом пространстве (вообще говоря, отличном от ). В случае, когда является случайным процессом с дискретным или непрерывным временем, аналогичным образом вводятся понятия пространства значений компонент сообщения на выходе и пространства значений отрезков длины псообщения на выходе. Мерой качества передачи сообщений по каналу связи является сообщений точность воспроизведения. Как правило, если передача ведется по каналу связи с помехами, даже если множества и совпадают, нельзя добиться абсолютной точности, т. е. полного совпадения посылаемого и получаемого сообщений. Обычно требования, предъявляемые к точности, трактуют статистически, выделяя класс Wдопустимых совместных распределений вероятностей для пары передаваемого и получаемого сообщений в множестве всех вероятностных мер в произведении Класс Wчасто задается при помощи измеримой неотрицательной функции и числа а>0: считают, что распределение вероятностей принадлежит W, лишь если Таким образом, условие точности воспроизведения показывает, насколько полученное сообщение может отличаться от переданного. Сообщения, вырабатываемые источником, передаются по каналу связи. Каналом (Q, V )наз. совокупность двух измеримых пространств переходной функции Q(y, А),. являющейся измеримой относительно s-алгебры Sпри фиксированном и вероятностной мерой на при фиксированном и подмножества Vв пространстве всех вероятностных мер в пространстве Пространства наз. соответственно пространствами сигналов на входе и выходе канала, а подмножество V- ограничением на распределение сигнала на входе. Говорят, что две случайные величины h. и (определенные на вероятностном пространстве связаны каналом (Q, V), если они принимают значения в соответственно и для любого с вероятностью 1 условная вероятность и распределение вероятностей случайной величины hпринадлежит V. Наиболее часто ограничение Vзадается с помощью измеримой функции p(у), и числа b>0: считают, что распределение вероятностей h принадлежит V, лишь если В случае дискретных каналов Vобычно совпадает с совокупностью всех распределений вероятностей, т. е. ограничение отсутствует. С наглядной точки зрения, — это совокупность сигналов, передаваемых передатчиком, а — совокупность сигналов, принимаемых приемником (в приложениях пространства и часто совпадают). Если задано случайное значение h. сигнала на входе, то (2) позволяет найти условное распределение сигнала на выходе h. Введение ограничения Vсвязано с тем, что во многих приложениях нельзя считать распределение входного сигнала произвольным [типична, напр., ситуация, когда предполагается, что среднее значение квадрата (мощность) входного сигнала не превосходит заданной константы]. В приложениях особенно важен случай, когда сигналами на входе и выходе канала являются случайные процессы h= , с дискретным или непрерывным временем, определенные на нек-ром конечном или бесконечном (в одну или обе стороны) интервале действительной оси и принимающие значения в нек-рых измеримых пространствах (Y, SY) и соответственно. Напр., если и — случайные последовательности, то канал связи, для к-рого последовательности h и h c волной служат сигналами на входе и выходе, часто рассматривают как последовательность каналов (в описанном выше смысле), называемых отрезками данного канала; сигналами на входе и выходе этих отрезков канала служат векторы Для того чтобы превратить сообщение на входе в сигнал, передаваемый по каналу связи, а сигнал, полученный на выходе канала,- в сообщение на выходе, необходимо провести операции кодирования и декодирования сообщений. Кодированием наз. функцию f(х). от со значениями в а декодированием — функцию от со значениями в Множество значений функции f(x), часто наз. кодом, а отдельные элементы этого множества — кодовыми словами. Использование кодирования f(x)и декодирования означает, что если сообщение приняло значение то по каналу передается сигнал y=f(x);если на выходе канала получен сигнал то его декодируют в сообщение на выходе В теории передачи информации часто рассматривают случайное кодирование, когда кодовые слова выбираются случайно в соответствии с нек-рым распределением вероятностей. Сообщение с распределением вероятностей р(Х), вырабатываемое источником, может быть передано с точностью воспроизведения Wпо каналу (Q, V )при помощи кодирования и декодирования если могут быть построены случайные величины x, h, образующие цепь Маркова такую, что x имеет распределение вероятностей распределение вероятностей пары принадлежит Wпара связана каналом (Q, V )и Предположение о том, что x, h, образуют цепь Маркова, сводится к предположению о том, что условное распределение при заданных значениях x и h зависит лишь от h, т. е. оно означает, что при передаче сигнал на выходе зависит лишь от сигнала на входе, а не от того, какое значение сообщения им закодировано. Основную проблему, исследуемую в И. п., можно сформулировать следующим образом. Считаются известными и фиксированными источник, порождающий сообщения с распределением вероятностей канал связи (Q, V )иусловия точности воспроизведения W. Задача состоит в том, чтобы выяснить, при каких условиях существуют методы кодирования и декодирования такие, что сообщение, вырабатываемое данным источником, может быть передано с заданной точностью воспроизведения Wпо данному каналу (Q, V). Решения этой проблемы при разных предположениях наз. теоремами кодирования, или теоремами Шеннона. Естественно возникает также другая проблема о том, как в случае, когда передача возможна, построить наиболее простым и эффективный образом кодирование и декодирование, осуществляющие эту передачу. К. Шеннон [1] ввел величины, позволяющие сформулировать ответ на первую из поставленных проблем. Главной среди них является информации количество, или просто информация, I(Х, Х). Если- пропускная способность канала (Q, V )(см. Канала пропускная способность), где верхняя грань берется по всем парам величин связанным каналом (Q, V), и если число есть W-энтропия (см. Энтропия )сообщения, где нижняя грань берется по всем парам таким, что совместное распределение вероятностей пары принадлежит W, а x имеет распределение вероятностей то справедлива следующая теорема Шеннона (обращение теоремы кодирования): если сообщение с распределением вероятностей может быть передано по каналу (Q, V )с условием точности воспроизведения W, то Достаточные условия для возможности И. п. получить сложнее. Так, условие (7) достаточно для возможности И. п. лишь в некотором асимптотпч. смысле, и при этом главным является предположение о том, что следовательно условие (7) необходимо и достаточно лишь, грубо говоря, применительно к задаче о передаче довольно большого количества информации. Остальные нужные предположения носят характер предположений регулярности, к-рые в конкретных ситуациях обычно выполняются. Чтобы сформулировать достаточные условия для возможности передачи в точных терминах, необходимы нек-рые дополнительные понятия. Последовательность пар случайных величин ( t=1,2, . . .) наз. информационно-устойчивой, если и в смысле сходимости по вероятности. Здесь -информационная плотность (см. Информации количество )пары Последовательность каналов с C(Qt, Vt)< наз. информационно-устойчивой, если существует информационно-устойчивая последовательность пар (ht, ht), связанных каналом (Qt, Vt), такая, что Последовательность сообщений с распределением вероятностей р t (Х) и условиями точности Wt с < t=1, 2, ..., наз. информационно-устойчивой, если существует последовательность пар (xt, xt) такая, что xt имеет распределение вероятностей распределение вероятностей пары (xt, xt) принадлежит Wt и Пусть Ve.- множество распределений вероятностей, для к-рого справедливо (3) с заменой bна b+e, a We — условие точности, задаваемое неравенством (1), в к-ром азаменено на а+e, e>0. Имеет место теорема кодирования (теорема Шеннона): пусть заданы информационно-устойчивая последовательность сообщений с распределением вероятностей pt (Х) и условиями точности Wt и информационно-устойчивая последовательность каналов , где отдельные компоненты (буквы сообщения xk) принимают значения из нек-рого конечного множества алфавита Xобъема М, производит буквы сообщения со скоростью одна буква в единицу времени. Компоненты сообщения получаемого адресатом, принимают значения из того же алфавита X(т. е. ). Пусть, далее, используется дискретный канал без памяти, передача по к-рому ведется со скоростью один символ в интервал времени т. Ограничения на распределение сигнала на входе канала отсутствуют. Пусть отрезок сообщения xL=(x1, ..., xL) длины L=LN передается по отрезку канала длины N=[L/t]. (где [х]- целая часть числа х)с помощью нек-рых методов кодирования и декодирования описанного выше типа. Если при этом =- соответствующий отрезок сообщения, полученный адресатом, а — средняя вероятность ошибки на букву источника, определяемая формулой то справедлива следующая теорема. Обращение теоремы кодирования. Пусть Н(U)-скорость создания сообщений данным дискретным стационарным источником и С — пропускная способность (на передаваемый символ) используемого канала без памяти. Тогда при всех Lсправедливо неравенство где Таким образом, если скорость создания сообщений Н(U)больше, чем (пропускная способность канала на букву источника), то средняя вероятность ошибки на букву источника при любом Lи для любых методов кодирования и декодирования ограничена снизу отличной от нуля константой и, значит, не стремится к нулю даже при Чтобы сформулировать прямое утверждение теоремы кодирования, необходима величина В случае, когда М=2 и LN/t- целое" число, RN=t, т. е. RN в битах является числом двоичных символов, вырабатываемых источником за время передачи одного символа по каналу. Кроме того, RN совпадает со скоростью создания сообщений Н(U)источником Uс независимыми и равномерно распределенными компонентами. Вероятность ошибки и средняя вероятность ошибки на блок источника определяются соответственно формулами: здесь Р xL(-)- условная вероятность при условии, что Справедлива следующая теорема кодирования. Для всех N и любого R<С существуют методы кодирования и декодирования такие, что при RN<R для всех xL О XL (оценка (17) справедлива и для Р e), причем для функция Е(R)выпуклая, положительная и убывает с ростом R(см. также Ошибочного декодирования вероятность). Таким образом, эта теорема показывает, что для всех R<C вероятность ошибки с ростом Nстремится к нулю и притом экспоненциально быстро. Имеются обобщения теорем Шеннона на случай так наз. составных каналов и сообщений с неизвестными параметрами. Интерес к подобным обобщениям вызван тем, что обычно на практике нельзя считать полностью известными статистич. параметры источника сообщений и канала связи, тем более что эти параметры могут иногда меняться в процессе передачи. Поэтому приходится предполагать, что источник сообщений и канал связи принадлежат нек-рому классу возможных источников сообщений и каналов. При этом вводится минимаксный критерий качества передачи, при к-ром качество данного метода передачи оценивается для наихудших возможных источников сообщений и каналов, принадлежащих рассматриваемому классу. Имеются также обобщения теорем Шеннона на случай И. п. по каналу с обратной связью. Наличие полной обратной связи означает, что в момент времени tна передающей стороне канала (т. е. на его входе) считаются известными точные значения сигналов на выходе канала для всех моментов времени t'<t. В частности, для каналов без памяти с обратной связью основной результат состоит в том, что наличие обратной связи не увеличивает пропускную способность канала, хотя и может существенно уменьшить сложность кодирующих и декодирующих устройств. Из других обобщений следует отметить теорию И. п. по каналам с ошибками синхронизации, в к-рых возможны случайные сбои синхронизации, в результате чего нарушается однозначность соответствия между сигналами на входе и выходе канала, а также теорию передачи по каналам многосторонним, когда имеется несколько источников и получателей информации и передача может осуществляться по нескольким направлениям одновременно. Лит.:[1] Шеннон К., Работы по теории информации и кибернетике, пер. с англ., М., 1963, с. 243-332; [2] Добрушин Р. Л., "Успехи матем. наук", 1959, т. 14, в. 6, с. 3-104; [3] Вольфовиц Дж., Теоремы кодирования теории информации, пер. с англ., М., 1967; [4] Галлагер Р., Теория информации и надежная связь, пер. с англ., М., 1974; [5] Файнстейн А., Основы теории информации, пер. с англ., М., 1960; [6] Фан о Р. М., Передача информации. Статистическая теория связи, пер. с англ., М., 1965; [7] Xаркевич А. А., Борьба с помехами, 2 изд., М., 1965; [8]Возенкрафт Д ж., Джекобе И., Теоретические основы техники связи, пер. с англ., М., 1969; [9] Колмогоров А. Н., "Пробл. передачи информ.", 1965, т. 1, № 1, с. 3-11; [10] Пинскер М. С, в сб.: Проблемы передачи информации, в. Я,1960, М., с. 1-201; [11] Левин Б. Р., Теоретические основы статистической радиотехники, 2 изд., М., 1974; [12] Колмогоров А. Н., в кн.: Сессия АН СССР по научным проблемам автоматизации производства. 15-20 октября 1956 г. Т. 1. Пленарные заседания, М., 1957, с. 66-99; [13] Key papers in the development of information theory, N.Y., 1974; [14] Proceeding of the 1975 IEEE-USSR Joint Workshop on Information Theory. Moscow. 15-19 December, 1975, N.Y., 1976. P. Л. Добрушин, В. В. Прелов.