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

- составная часть информации теории, относящаяся к изучению процесса переноса информации от источника сообщений к получателю сообщений (адресату). В теории И. п. изучаются оптимальные и близкие к оптимальным методы И. п. по каналам связи в предположении, что можно в широких пределах варьировать методы кодирования сообщений в сигналы на входе канала и декодирования сигналов на выходе канала в сообщения на выходе (см. Кодирование и декодирование). Общую схему системы И. п., впервые рассмотренную К. Шенноном (С. Shannon, [1]), можно описать следующим образом. Источник сообщений вырабатывает сообщения, подлежащие передаче по каналу связи от источника к получателю. Обычно предполагают, что это сообщение - случайная величина x, определенная на нек-ром вероятностном пространстве(W, U, Р), принимающая значения в нек-ром измеримом пространстве [img: http://localhost:8080/file/021019-8.jpg] и имеющая распределение вероятностей р(-). Часто [img: http://localhost:8080/file/021019-9.jpg] где D - множество значений параметра t, является случайным процессом с дискретным или непрерывным временем со значениями в нек-ром измеримом пространстве (X, SX)-Напр., в случае дискретного времени x= {xk, k=l, 2,...} или x={xk, k=..., -1, 0, 1,...} случайные величины xk, принимающие значения в измеримом пространстве (X, SX), наз. компонентами сообщения на входе и часто трактуются как сообщения, вырабатываемые источником в моменты времени k. Наборы x п= (x1,..., x п), принимающие значения в пространстве (Х п, SXn), т. е. в n-кратном произведении пространств (X, SX), паз. отрезками сообщений длины пна входе. Аналогичным образом определяются соответствующие понятия и в случае, когда сообщение - случайный процесс с непрерывным временем. Сообщение на выходе, получаемое адресатом,- это тоже случайная величина [img: http://localhost:8080/file/021019-10.jpg] определенная на том же вероятностном пространстве [img: http://localhost:8080/file/021019-11.jpg] и принимающая значения в измеримом пространстве [img: http://localhost:8080/file/021019-12.jpg] (вообще говоря, отличном от [img: http://localhost:8080/file/021019-13.jpg]). В случае, когда [img: http://localhost:8080/file/021019-14.jpg] является случайным процессом с дискретным или непрерывным временем, аналогичным образом вводятся понятия пространства [img: http://localhost:8080/file/021019-15.jpg] значений компонент сообщения на выходе и пространства [img: http://localhost:8080/file/021019-16.jpg] значений отрезков длины псообщения на выходе. Мерой качества передачи сообщений по каналу связи является сообщений точность воспроизведения. Как правило, если передача ведется по каналу связи с помехами, даже если множества [img: http://localhost:8080/file/021019-17.jpg] и [img: http://localhost:8080/file/021019-18.jpg] совпадают, нельзя добиться абсолютной точности, т. е. полного совпадения посылаемого и получаемого сообщений. Обычно требования, предъявляемые к точности, трактуют статистически, выделяя класс Wдопустимых совместных распределений вероятностей для пары [img: http://localhost:8080/file/021019-19.jpg] передаваемого и получаемого сообщений в множестве всех вероятностных мер в произведении [img: http://localhost:8080/file/021019-20.jpg] Класс Wчасто задается при помощи измеримой неотрицательной функции [img: http://localhost:8080/file/021019-21.jpg] и числа а>0: считают, что распределение вероятностей [img: http://localhost:8080/file/021019-22.jpg] принадлежит W, лишь если [img: http://localhost:8080/file/021019-23.jpg] Таким образом, условие точности воспроизведения показывает, насколько полученное сообщение может отличаться от переданного. Сообщения, вырабатываемые источником, передаются по каналу связи. Каналом (Q, V)наз. совокупность двух измеримых пространств [img: http://localhost:8080/file/021019-24.jpg] переходной функции Q(y, А), [img: http://localhost:8080/file/021019-25.jpg]. являющейся измеримой относительно s-алгебры Sпри фиксированном [img: http://localhost:8080/file/021019-26.jpg] и вероятностной мерой на [img: http://localhost:8080/file/021019-27.jpg] при фиксированном [img: http://localhost:8080/file/021019-28.jpg] и подмножества Vв пространстве всех вероятностных мер в пространстве [img: http://localhost:8080/file/021019-29.jpg] Пространства [img: http://localhost:8080/file/021019-30.jpg] наз. соответственно пространствами сигналов на входе и выходе канала, а подмножество V- ограничением на распределение сигнала на входе. Говорят, что две случайные величины h. и [img: http://localhost:8080/file/021019-31.jpg] (определенные на вероятностном пространстве [img: http://localhost:8080/file/021019-32.jpg] связаны каналом (Q, V), если они принимают значения в [img: http://localhost:8080/file/021019-33.jpg] соответственно и для любого [img: http://localhost:8080/file/021019-34.jpg] с вероятностью 1 условная вероятность [img: http://localhost:8080/file/021019-35.jpg] и распределение вероятностей случайной величины hпринадлежит V. Наиболее часто ограничение Vзадается с помощью измеримой функции p(у), [img: http://localhost:8080/file/021019-36.jpg] и числа b>0: считают, что распределение вероятностей h принадлежит V, лишь если [img: http://localhost:8080/file/021019-37.jpg] В случае дискретных каналов Vобычно совпадает с совокупностью всех распределений вероятностей, т. е. ограничение отсутствует. С наглядной точки зрения, [img: http://localhost:8080/file/021019-38.jpg] - это совокупность сигналов, передаваемых передатчиком, а [img: http://localhost:8080/file/021019-39.jpg] - совокупность сигналов, принимаемых приемником (в приложениях пространства [img: http://localhost:8080/file/021019-40.jpg] и часто [img: http://localhost:8080/file/021019-41.jpg] совпадают). Если задано случайное значение h. сигнала на входе, то (2) позволяет найти условное распределение сигнала на выходе h. Введение ограничения Vсвязано с тем, что во многих приложениях нельзя считать распределение входного сигнала произвольным [типична, напр., ситуация, когда предполагается, что среднее значение квадрата (мощность) входного сигнала не превосходит заданной константы]. В приложениях особенно важен случай, когда сигналами на входе и выходе канала являются случайные процессы h= {h(t)}, [img: http://localhost:8080/file/021019-42.jpg] с дискретным или непрерывным временем, определенные на нек-ром конечном или бесконечном (в одну или обе стороны) интервале действительной оси и принимающие значения в нек-рых измеримых пространствах (Y, SY) и [img: http://localhost:8080/file/021019-43.jpg] соответственно. Напр., если h={h1, h1,...} и [img: http://localhost:8080/file/021019-44.jpg] - случайные последовательности, то канал связи, для к-рого последовательности h и h c волной служат сигналами на входе и выходе, часто рассматривают как последовательность каналов (в описанном выше смысле), называемых отрезками данного канала; сигналами на входе и выходе этих отрезков канала служат векторы [img: http://localhost:8080/file/021019-45.jpg] Для того чтобы превратить сообщение на входе в сигнал, передаваемый по каналу связи, а сигнал, полученный на выходе канала,- в сообщение на выходе, необходимо провести операции кодирования и декодирования сообщений. Кодированием наз. функцию f(х). от [img: http://localhost:8080/file/021019-46.jpg] со значениями в [img: http://localhost:8080/file/021019-47.jpg] а декодированием - функцию [img: http://localhost:8080/file/021019-48.jpg] от [img: http://localhost:8080/file/021019-49.jpg] со значениями в [img: http://localhost:8080/file/021019-50.jpg] Множество значений функции f(x), [img: http://localhost:8080/file/021019-51.jpg] часто наз. кодом, а отдельные элементы этого множества - кодовыми словами. Использование кодирования f(x)и декодирования [img: http://localhost:8080/file/021019-52.jpg] означает, что если сообщение приняло значение [img: http://localhost:8080/file/021019-53.jpg] то по каналу передается сигнал y=f(x);если на выходе канала получен сигнал [img: http://localhost:8080/file/021019-54.jpg] то его декодируют в сообщение на выходе [img: http://localhost:8080/file/021019-55.jpg] В теории передачи информации часто рассматривают случайное кодирование, когда кодовые слова выбираются случайно в соответствии с нек-рым распределением вероятностей. Сообщение с распределением вероятностей р(Х), вырабатываемое источником, может быть передано с точностью воспроизведения Wпо каналу (Q, V)при помощи кодирования [img: http://localhost:8080/file/021019-56.jpg] и декодирования [img: http://localhost:8080/file/021019-57.jpg] если могут быть построены случайные величины x, h, [img: http://localhost:8080/file/021019-58.jpg] [img: http://localhost:8080/file/021019-59.jpg] образующие цепь Маркова такую, что x имеет распределение вероятностей [img: http://localhost:8080/file/021019-60.jpg] распределение вероятностей пары [img: http://localhost:8080/file/021019-61.jpg] принадлежит Wпара [img: http://localhost:8080/file/021019-62.jpg] связана каналом (Q, V)и [img: http://localhost:8080/file/021019-63.jpg] Предположение о том, что x, h, [img: http://localhost:8080/file/021019-64.jpg] образуют цепь Маркова, сводится к предположению о том, что условное распределение [img: http://localhost:8080/file/021019-65.jpg] при заданных значениях x и h зависит лишь от h, т. е. оно означает, что при передаче сигнал на выходе зависит лишь от сигнала на входе, а не от того, какое значение сообщения им закодировано. Основную проблему, исследуемую в И. п., можно сформулировать следующим образом. Считаются известными и фиксированными источник, порождающий сообщения с распределением вероятностей [img: http://localhost:8080/file/021019-66.jpg] канал связи (Q, V)иусловия точности воспроизведения W. Задача состоит в том, чтобы выяснить, при каких условиях существуют методы кодирования [img: http://localhost:8080/file/021019-67.jpg] и декодирования [img: http://localhost:8080/file/021019-68.jpg] такие, что сообщение, вырабатываемое данным источником, может быть передано с заданной точностью воспроизведения Wпо данному каналу (Q, V). Решения этой проблемы при разных предположениях наз. теоремами кодирования, или теоремами Шеннона. Естественно возникает также другая проблема о том, как в случае, когда передача возможна, построить наиболее простым и эффективный образом кодирование и декодирование, осуществляющие эту передачу. К. Шеннон [1] ввел величины, позволяющие сформулировать ответ на первую из поставленных проблем. Главной среди них является информации количество, или просто информация, I(Х, Х). Если [img: http://localhost:8080/file/021019-69.jpg] - пропускная способность канала (Q, V)(см. Канала пропускная способность), где верхняя грань берется по всем парам величин [img: http://localhost:8080/file/021019-70.jpg] связанным каналом (Q, V), и если число [img: http://localhost:8080/file/021019-71.jpg] есть W-энтропия (см. Энтропия)сообщения, где нижняя грань берется по всем парам [img: http://localhost:8080/file/021019-72.jpg] таким, что совместное распределение вероятностей пары [img: http://localhost:8080/file/021019-73.jpg] принадлежит W, а x имеет распределение вероятностей [img: http://localhost:8080/file/021019-74.jpg] то справедлива следующая теорема Шеннона (обращение теоремы кодирования): если сообщение с распределением вероятностей [img: http://localhost:8080/file/021019-75.jpg] может быть передано по каналу (Q, V)с условием точности воспроизведения W, то [img: http://localhost:8080/file/021019-76.jpg] Достаточные условия для возможности И. п. получить сложнее. Так, условие (7) достаточно для возможности И. п. лишь в некотором асимптотпч. смысле, и при этом главным является предположение о том, что [img: http://localhost:8080/file/021019-77.jpg] следовательно условие (7) необходимо и достаточно лишь, грубо говоря, применительно к задаче о передаче довольно большого количества информации. Остальные нужные предположения носят характер предположений регулярности, к-рые в конкретных ситуациях обычно выполняются. Чтобы сформулировать достаточные условия для возможности передачи в точных терминах, необходимы нек-рые дополнительные понятия. Последовательность пар случайных величин ([img: http://localhost:8080/file/021019-78.jpg] t=1,2,...) наз. информационно-устойчивой, если [img: http://localhost:8080/file/021019-79.jpg] и [img: http://localhost:8080/file/021019-80.jpg] в смысле сходимости по вероятности. Здесь [img: http://localhost:8080/file/021019-81.jpg] -информационная плотность (см. Информации количество)пары [img: http://localhost:8080/file/021019-82.jpg] Последовательность каналов {(Qt, Vt), t=1,2,...} с C(Qt, Vt)< [img: http://localhost:8080/file/021019-83.jpg] наз. информационно-устойчивой, если существует информационно-устойчивая последовательность пар (ht, ht), связанных каналом (Qt, Vt), такая, что [img: http://localhost:8080/file/021019-84.jpg] Последовательность сообщений с распределением вероятностей р t (Х) и условиями точности Wt с [img: http://localhost:8080/file/021019-85.jpg] < [img: http://localhost:8080/file/021019-86.jpg] t=1, 2,..., наз. информационно-устойчивой, если существует последовательность пар (xt, xt) такая, что xt имеет распределение вероятностей [img: http://localhost:8080/file/021019-87.jpg] распределение вероятностей пары (xt, xt) принадлежит Wt и [img: http://localhost:8080/file/021019-88.jpg] Пусть Ve.- множество распределений вероятностей, для к-рого справедливо (3) с заменой bна b+e, a We - условие точности, задаваемое неравенством (1), в к-ром азаменено на а+e, e>0. Имеет место теорема кодирования (теорема Шеннона): пусть заданы информационно-устойчивая последовательность сообщений с распределением вероятностей pt (Х) и условиями точности Wt и информационно-устойчивая последовательность каналов {Qt, Vt)такие, что функции [img: http://localhost:8080/file/021019-89.jpg] и [img: http://localhost:8080/file/021019-90.jpg] равномерно ограничены по t;пусть [img: http://localhost:8080/file/021019-91.jpg] при [img: http://localhost:8080/file/021019-92.jpg] и [img: http://localhost:8080/file/021019-93.jpg] тогда для любого е>0 существует столь большое t0, что при всех [img: http://localhost:8080/file/021019-94.jpg] сообщение с распределением вероятностей [img: http://localhost:8080/file/021019-95.jpg] может быть передано через канал (Qt, vte). с точностью воспроизведения [img: http://localhost:8080/file/021019-96.jpg] Эта формулировка прямого утверждения теоремы кодирования является одной из наиболее общих. Предположение об ограниченности функций [img: http://localhost:8080/file/021019-97.jpg] и ' [img: http://localhost:8080/file/021019-98.jpg] может быть существенно ослаблено. Информационная устойчивость последовательности сообщений и каналов всегда имеет место в большом числе практически интересных частных случаев. Наконец, при нек-рых условиях в сформулированной теореме можно заменить [img: http://localhost:8080/file/021019-99.jpg] на [img: http://localhost:8080/file/021019-100.jpg] и [img: http://localhost:8080/file/021019-101.jpg] на Vt. Для описания реальных ситуаций наиболее интересен случай, когда последовательность каналов, рассматриваемая в теореме, есть последовательность отрезков данного фиксированного канала, а последовательность сообщений - это последовательность отрезков сообщений фиксированного источника с растущим числом компонент. Наглядно это соответствует функционированию системы связи во времени. Ниже для этой ситуации сформулированы нек-рый вариант теоремы кодирования и его обращение в несколько отличной от предыдущей форме. При этом рассматриваются дискретный стационарный источник и канал без памяти. Пусть дискретный стационарный источник U, вырабатывающий сообщение x={xk, k=...,- 1, 0, 1,...}, где отдельные компоненты (буквы сообщения xk) принимают значения из нек-рого конечного множества алфавита Xобъема М, производит буквы сообщения со скоростью одна буква в единицу времени. Компоненты сообщения [img: http://localhost:8080/file/021019-102.jpg] получаемого адресатом, принимают значения из того же алфавита X(т. е. [img: http://localhost:8080/file/021019-103.jpg]). Пусть, далее, используется дискретный канал без памяти, передача по к-рому ведется со скоростью один символ в интервал времени т. Ограничения на распределение сигнала на входе канала отсутствуют. Пусть отрезок сообщения xL=(x1,..., xL) длины L=LN передается по отрезку канала длины N=[L/t]. (где [х]- целая часть числа х)с помощью нек-рых методов кодирования и декодирования описанного выше типа. Если при этом [img: http://localhost:8080/file/021019-104.jpg] = [img: http://localhost:8080/file/021019-105.jpg] - соответствующий отрезок сообщения, полученный адресатом, а [img: http://localhost:8080/file/021019-106.jpg] - средняя вероятность ошибки на букву источника, определяемая формулой [img: http://localhost:8080/file/021019-107.jpg] то справедлива следующая теорема. Обращение теоремы кодирования. Пусть Н(U)-скорость создания сообщений данным дискретным стационарным источником и С - пропускная способность (на передаваемый символ) используемого канала без памяти. Тогда при всех Lсправедливо неравенство [img: http://localhost:8080/file/021019-108.jpg] где [img: http://localhost:8080/file/021019-109.jpg] Таким образом, если скорость создания сообщений Н(U)больше, чем [img: http://localhost:8080/file/021019-110.jpg] (пропускная способность канала на букву источника), то средняя вероятность ошибки на букву источника при любом Lи для любых методов кодирования и декодирования ограничена снизу отличной от нуля константой и, значит, не стремится к нулю даже при [img: http://localhost:8080/file/021019-111.jpg] Чтобы сформулировать прямое утверждение теоремы кодирования, необходима величина [img: http://localhost:8080/file/021019-112.jpg] В случае, когда М=2 и LN/t- целое" число, RN=t, т. е. RN в битах является числом двоичных символов, вырабатываемых источником за время передачи одного символа по каналу. Кроме того, RN совпадает со скоростью создания сообщений Н(U)источником Uс независимыми и равномерно распределенными компонентами. Вероятность ошибки и средняя вероятность ошибки на блок источника определяются соответственно формулами: [img: http://localhost:8080/file/021019-113.jpg] здесь Р xL(-)- условная вероятность при условии, что [img: http://localhost:8080/file/021019-114.jpg] Справедлива следующая теорема кодирования. Для всех N и любого R<С существуют методы кодирования и декодирования такие, что при RN<R для всех xL О XL [img: http://localhost:8080/file/021019-115.jpg] (оценка (17) справедлива и для Р e), причем для [img: http://localhost:8080/file/021019-116.jpg] функция Е(R)выпуклая, положительная и убывает с ростом R(см. также Ошибочного декодирования вероятность). Таким образом, эта теорема показывает, что для всех R<C вероятность ошибки с ростом Nстремится к нулю и притом экспоненциально быстро. Имеются обобщения теорем Шеннона на случай так наз. составных каналов и сообщений с неизвестными параметрами. Интерес к подобным обобщениям вызван тем, что обычно на практике нельзя считать полностью известными статистич. параметры источника сообщений и канала связи, тем более что эти параметры могут иногда меняться в процессе передачи. Поэтому приходится предполагать, что источник сообщений и канал связи принадлежат нек-рому классу возможных источников сообщений и каналов. При этом вводится минимаксный критерий качества передачи, при к-ром качество данного метода передачи оценивается для наихудших возможных источников сообщений и каналов, принадлежащих рассматриваемому классу. Имеются также обобщения теорем Шеннона на случай И. п. по каналу с обратной связью. Наличие полной обратной связи означает, что в момент времени tна передающей стороне канала (т. е. на его входе) считаются известными точные значения сигналов на выходе канала для всех моментов времени t'<t. В частности, для каналов без памяти с обратной связью основной результат состоит в том, что наличие обратной связи не увеличивает пропускную способность канала, хотя и может существенно уменьшить сложность кодирующих и декодирующих устройств. Из других обобщений следует отметить теорию И. п. по каналам с ошибками синхронизации, в к-рых возможны случайные сбои синхронизации, в результате чего нарушается однозначность соответствия между сигналами на входе и выходе канала, а также теорию передачи по каналам многосторонним, когда имеется несколько источников и получателей информации и передача может осуществляться по нескольким направлениям одновременно.