Канал (в теории информации)
Канал (в теории информации)
Канал в теории информации, всякое устройство, предназначенное для передачи информации. В отличие от техники, информации теория отвлекается от конкретной природы этих устройств, подобно тому как геометрия изучает объёмы тел, отвлекаясь от материала, из которого они изготовлены (ср. Канал технич.). Различные конкретные системы связи рассматриваются в теории информации только с точки зрения количества информации, которое может быть надёжно передано с их помощью. Т. о. приходят к понятию К.: канал задаётся множеством "допустимых" сообщений (или сигналов) x на входе, множеством сообщений (сигналов) у на выходе и набором условных вероятностей р (у|х) получения сигнала у на выходе при входном сигнале х. Условные вероятности р (у|х) описывают статистические свойства "шумов" (помех), искажающих сигналы в процессе передачи. В случае, когда р (у|х) = 1 при у = х и р (y|x) = 0 при у ¹ х, К. называют каналом без "шумов". В соответствии со структурой входных и выходных сигналов выделяют К. дискретные и К. непрерывные. В дискретных К. сигналы на входе и на выходе представляют собой последовательности "букв" из одного и того же или различных "алфавитов" (см. Код). В непрерывных К. входной и выходной сигналы суть функции непрерывного параметра t - времени. Возможны также смешанные случаи, но обычно в качестве идеализации предпочитают рассматривать один из указанных двух случаев.
Способность К. передавать информацию характеризуется некоторым числом - пропускной способностью, или ёмкостью, К., которое определяется как максимальное количество информации относительно сигнала на входе, содержащееся в сигнале на выходе (в расчёте на единицу времени).
Точнее: пусть входной сигнал x принимает некоторые значения х с вероятностями р (х). Тогда по формулам теории вероятностей можно рассчитать как вероятности q (y) того, что сигнал h на выходе примет значение у:
так и вероятности р (х, y) совмещения событий x = х, h = у: р (х, у) = р (х) р (у|х).
По этим последним вычисляется количество информации (в двоичных единицах) и его среднее значение ,
где T - длительность x. Верхняя граница С величин R, взятая по всем допустимым сигналам на входе, называют ёмкостью К. Вычисление ёмкости, подобно вычислению энтропии, легче в дискретном случае и значительно сложнее в непрерывном, где оно основывается на теории стационарных случайных процессов.
Проще всего положение в случае дискретного К. без "шумов". В теории информации устанавливается, что в этом случае общее определение ёмкости С равносильно следующему:
где N (T) - число допустимых сигналов длительностью Т.
Пример 1. Пусть "алфавит" К. без "шумов" состоит из двух "букв" - 0 и 1, длительностью t сек каждая. Допустимые сигналы длительностью Т = nt представляются последовательностями символов 0 и 1. Их число N (Т) = 2n. Соответственно - двоичных единиц/сек.
Пример 2. Пусть символы 0 и 1 имеют длительность t и 2t сек соответственно. Здесь допустимых сигналов длительностью Т = nt будет меньше, чем в примере 1. Так, при n = 3 их будет всего 3 (вместо 8). Можно подсчитать теперь двоичных единиц/сек.
При необходимости передачи записанных с помощью некоторого кода сообщений по данному К. приходится преобразовывать эти сообщения в допустимые сигналы К., т. е. производить надлежащее кодирование. После передачи надо произвести операцию декодирования, т. е. операцию обратного преобразования сигнала в сообщение. Естественно, что кодирование целесообразно производить так, чтобы среднее время, затрачиваемое на передачу, было возможно меньше. При одинаковой длительности символов на входе К. это означает, что надо выбирать наиболее экономный код с "алфавитом", совпадающим с входным "алфавитом" К.
При описанной процедуре "согласования" источника с К. возникает специфическое явление задержки (запаздывания), которое может пояснить следующий пример.
Пример 3. Пусть источник сообщений посылает через промежутки времени длиной 1/u (т. е. со скоростью u) независимые символы, принимающие значения x1, x2, x3, x4 свероятностями, равными соответственно 1/2, 1/4, 1/8, 1/8. Пусть К. без "шумов" такой же, как в примере 1, и кодирование осуществляется мгновенно. Полученный сигнал или передаётся по К., если последний свободен, или ожидает (помещается в "память") до тех пор, пока К. не освободится. Если теперь выбран, например, код x1 = 00, x2 = 01, x3 = 10, x4 = 11 и u £ 1/2t (т. е. 1/u ³ 2t), то за время между появлением двух последовательных значений х кодовое обозначение успевает передаться и К. освобождается. Т. о., здесь между появлением какой-либо "буквы" сообщения и передачей ее кодового обозначения по К. проходит промежуток времени 2t. Иная картина наблюдается при u > 1/2t; n-я "буква" сообщения появляется в момент (n - 1)/u и её кодовое обозначение будет передано по К. в момент 2nt. Следовательно, промежуток времени между появлением n-й "буквы" сообщения и моментом её получения после декодирования переданного сигнала будет больше, чем n (2t - 1/u), что стремится к бесконечности при n ° ¥. Таким образом, в этом случае передача будет вестись с неограниченным запаздыванием. Стало быть, для возможности передачи без неограниченного запаздывания при данном коде необходимо и достаточно выполнение неравенства u £ 1/2t. Выбором более удачного кода можно увеличить скорость передачи, сделав её сколь угодно близкой к ёмкости К., но эту последнюю границу невозможно превзойти (разумеется, сохраняя требование ограниченности запаздывания). Сформулированное утверждение имеет совершенно общий характер и называется основной теоремой о К. без "шумов".
Специально в отношении примера 3 уместно добавить следующее. Для рассматриваемых сообщений двоичный код x1 = 0, x2 = 10, x3 = 110, x4 = 111 оптимален. Из-за различной длины кодовых обозначений время wn запаздывания для n-й "буквы" первоначального сообщения будет случайной величиной. При u < 1/t (1/t - ёмкость К.) и n ° ¥ его среднее значение приближается к некоторому пределу m(u), зависящему от u. С приближением u к критическому значению 1/t значение m(u) растет пропорционально (t-1 - u)-1. Это опять-таки отражает общее положение: стремление сделать скорость передачи возможно ближе к максимальной сопровождается возрастанием времени запаздывания и необходимого объёма "памяти" кодирующего устройства.
Утверждение "основной теоремы" (с заменой безошибочной передачи на "почти безошибочную") справедливо и для К. с "шумами". Этот факт, по существу основной для всей теории передачи информации, называют теоремой Шеннона (см. Шеннона теорема). Возможность уменьшения вероятности ошибочной передачи через К. с "шумами" достигается применением так называемых помехоустойчивых кодов.
Пример 4. Пусть входной "алфавит" К. состоит из двух символов 0 и 1 и действие "шумов" сводится к тому, что каждый из этих символов при передаче может с небольшой (например, равной 1/10) вероятностью р перейти в другой или с вероятностью q = 1 - р остаться неискажённым. Применение помехоустойчивого кода сводится, по сути дела, к выбору нового "алфавита" на входе К. Его "буквами" являются n-членные цепочки символов 0 и 1, отличающиеся одна от другой достаточным числом D знаков. Так, при n = 5 и D = 3 новыми "буквами" могут быть 00000, 01110, 10101, 11011. Если вероятность более чем одной ошибки на группу из пяти знаков мала, то даже искажённые эти новые "буквы" почти не перепутываются. Например, если получен сигнал 10001, то он почти наверное возник из 10101. Оказывается, что при надлежащем подборе достаточно больших n и D такой способ значительно эффективнее простого повторения (т. е. использования "алфавитов" типа 000, 111). Однако возможное на этом пути улучшение процесса передачи неизбежно сопряжено с сильно возрастающей сложностью кодирующих и декодирующих устройств. Например, подсчитано, что если первоначально р = 10-2 и требуется уменьшить это значение до p1 = 10-4, то следует выбирать длину nкодовой цепочки не менее 25 (или 380) в зависимости от того, желают ли использовать ёмкость К. на 53% (или на 80%).
Лит. см. при ст. информации теория.
Ю. В. Прохоров.