Пятый постулат теории информации

Вернёмся к рис. 4. Пусть матрица соответствия Π = || π _{j k}; j, k = 1, 2, …, N || диагонализируема ( | det Π | = 1), так что в отсутствие в канале КПДС помех статическая система передачи информации абсолютно надёжна [ = 1] и потери информации в системе ССПИ не происходит, а между символами {w_j} и знаками {u_j} имеется одно-однозначное соответствие.

Из-за наличия в реальных каналах КПДС (в основном – в линиях электросвязи) различного рода естественных и искусственных помех это одно-однозначное соответствие непредсказуемым (случайным) образом нарушается. В простейшем варианте системы ССПИ (см. рис. 5) стохастичность каналаКПДС можно характеризовать квадратной переходной матрицей порядка NП= || P_{j k}; j, k = 1, 2, …, N ||, элементы которой P_{j k} = P (w_k|u_j) есть условные вероятности того, что входному (первичному) знаку u_j U будет соответствовать (при сканировании произвольного текста) выходной символ w_k W. При любом значении j = 1, 2, …, N соблюдается равенство , то есть элементарное сообщение u_j в любом случае как-то идентифицируется (решение на выходе декодера: «Не знаю, что за знак был передан по каналу КПДС!» – не принимается). По формуле полной вероятности .

Понятно, что если переходная матрицаПимеет диагональный вид, то есть П= || δ_{j k}; j, k = 1, 2, …, N ||, где δ_{j k} = 1 при j = k и δ_{j k} = 0 при j ≠ k (δ_{j k} – символ Кронекера), то символу w_k всегда будет присваиваться значение знака u_k – и потерь информации в канале КПДС происходить не будет. Такие системы ССПИ рассматривались в разд. 6.

В общем случае матрицаП– произвольная, с двумя ограничениями:

а) 0 ≤ P_{j k} ≤ 1;

б ) = 1 при любом j = 1, 2, …, N.

помехи

Π = { P_{j k} }

U = {u_j} P₁₁ P₁₂ … P_{1 k} … P_{1 N} W = {w_k}

P = {P_j} P₂₁ P₂₂ … P_{2 k} … P_{2 N} P_вых = {P'_k}

I = {I_j} . . . . . . . . . . . . . . . . . . . I_вых ={I'_{k j}; j, k = 1, 2, …, N }

= – P_{j 1} P_{j 2} … P_{j k} … P_{j N}

. . . . . . . . . . . . . . . . . . . .

P_{N 1} P_{N 2} … P_{N k} … P_{N N}

Рис. 5. Статическая система передачи

дискретной информации при наличии помех

Отметим также, что величина (сумма элементов k-го столбца матрицы П) может лежать в пределах от 0 до N при любом k = 1, …, N, то есть в крайних случаях либо k-му символу w_k не будет присвоено ни одного из значений переданных знаков u_j U, либо всем им будет соответствовать выходной символ w_k.

Каким же образом символу w_k W на выходе КПДС следует присваивать значение некоторого знака u_j U? Оптимальным решением, с точки зрения математическойстатистики, будет следующее: символу w_k нужно присваивать значение u_j, апостериорная вероятность которого

P(u_j|w_k) = P(u_j) P(w_k|u_j)/P(w_k) = P_j P_jk /P'_k

максимальна по всем значениям j = 1, 2, …, N (байесовское решение). В этом случае информационные потери в канале КПДС должны быть минимальными.

Переставим столбцы матрицы П в соответствии с этим правилом принятия решения таким образом, чтобы k-й выходной символ w_k соответствовал k-му знаку u_k на входеканала КПДС. Тогда знаку u_j чаще всего (но не всегда!) будет соответствовать символ w_j.

При произвольной матрице П сообщение S_i⁽ⁿ⁾ = ( u_i1, u_i2, …, u_ik, …, u_in ) будет доходить до получателя ПИ в искажённом виде S'_i⁽ⁿ⁾ = ( w_i1, w_i2, …, w_ik, …, w_in ), поскольку в общем случае любому символу w_ik может быть случайным образом присвоено значение любого знака u_j. Поэтому возникает вопрос: насколько эти искажения существенны? Поскольку нас интересуют «длинные сообщения» (S_i⁽ⁿ⁾, n >> 1), у которых I(S_i⁽ⁿ⁾) ≈ n ≡ n H(U), то в простейшем случае, когда помехи в канале КПДС не зависят от знаков u_j U, нам нужно определить среднюю (на один входной знак u_j) потерю синтактической информации при ошибочной идентификации знаков {u_j} источника ДИС на выходе канала КПДС.

Казалось бы, количество информации I_{j j}, которое содержится в выходном символе w_j, относительно информации, содержащейся во входном знаке u_j – после упорядочения («квазидиагонализации») матрицы П = || P_{j k} || в соответствии с байесовским правилом идентификации символов w_k – можно вычислить по формуле I_{j j} = P_{j j} I_j = – P_{j j} log P_j. Тогда «естественным образом» получается:

при P_{j j} = 1 величина I_{j j} = I_j = – log P_j, а при P_{j j} = 0: I_{j j} = 0.

Однако это не так, ибо отсутствие в выходном символе w_k информации о входном знаке u_j соответствует не случаю, когда P_{j k} = P(w_k|u_j) = 0, а случаю, когда вероятность P_{j k} появления на выходе КПДС символа w_k не связано статистически с появлением знака u_j на его входе, то есть когда

P_{j k} = P(w_k|u_j) = P(w_k) = P'_k, или .

Поскольку P(u_j, w_k) = P(u_j) P(w_k|u_j) = P(w_k) P(u_j|w_k), то

,

и при P(w_k|u_j) = P(w_k), или, что то же самое, при P_jk = P'_k справедливо равенство: P(u_j|w_k) = P(u_j).

Если у симметричного бинарного канала КПДС P(w_k|u_j) = 0,5 = P(w_k), то,

как остроумно заметил К. Шеннон ([46], с. 227), линия электросвязи в КПДС вовсе не нужна: получатель информации ПИ может с таким же успехом подбрасывать монету. И хотя половина знаков u_j будет идентифицирована на выходе канала КПДС правильно, какие из символов w_ik в последовательности S'_i⁽ⁿ⁾ = (w_i1, w_i2, …, w_ik, …, w_in ) будут соответствовать знакам u_j, а какие – нет, получатель информации определить не сможет. В этом случае

P(w_k|u_j) = P(w_k), или P_{j k} /P'_k = 1, или log(P_{j k} /P'_k ) = – log(P'_k /P_{j k}) = 0.

Значит,

величиной Ik j = log(Pj k /P'k) можно характеризовать количество информации, содержащейся в выходном символе wk W относительно входного знака uj U.

Если при всех значениях j и k от 1 до N величина P_{j k} принимает значение либо P_{j k} = 1, либо P_{j k} = 0 (то есть P_{j k} = π _{j k}), то мы приходим к вариантам, рассмотренным нами в разд. 6: I_{k j} = log(π _{j k} /P'_k).

Особенно ясно это видно при анализе потерь информации в бинарных системах передачи сообщений.

Пусть имеется бинарный канал КПДС. Его функционирование можно описать схемой, представленной на рис. 6. Введём следующие обозначения:

P₁ = P, P₂ = 1 – P, P₁₁ = p, P₁₂ = 1 – p, P₂₂ = q, P₂₁ = 1 – q,

I_{k j} = log(P_{j k} /P'_k); j, k = 1, 2;

P'₁ = P p + (1 – P) (1 – q), P'₂ = P (1 – p) + (1 – P) q.

Удельная информативность знаков (энтропия) бинарного источника ДИС

.

Рассмотрим случай а) на рис. 6: p = 1, q = 1, p + q = 2. В этом случае потерь информации нет, и среднее количество информации, содержащейся на выходе канала КПДС относительно источника ДИС, определяется из следующих

P₁₁ = p

(P₁ = P ) u₁ →¤ ¤→ w₁ (P'₁)

P₁₂ = 1 – p P₂₁ = 1 – q

(P₂ = 1 – P ) u₂ →¤ ¤→ w₂ (P'₂ = 1 – P' )

P₂₂ = q

p = 1 p = 0 p = 0

u₁ →¤ ¤→ w₁ u₁ →¤ ¤→ w₁ u₁ →¤ ¤→ w₁

u₂ →¤ ¤→ w₂ u₂ →¤ ¤→ w₂ u₂ →¤ ¤→ w₂

q = 1 q = 0 q = 1

а) б ) в)

p = 0,5

u₁ →¤ ¤→ w₁

0,5

0,5

u₂ →¤ ¤→ w₂

q = 0,5

г)

Рис. 6. Бинарный канал передачи дискретных сообщений

вычислений – в соответствии с формулой (6.2):

P'₁ = P; P'₂= 1 – P;

P₁ P₁₁ I₁₁ = – P log P; P₁ P₁₂ I₂₁ = – P·0·log 0 = 0;

P₂ P₂₁ I₁₂ = – (1 – P)·0·log 0; P₂ P₂₂ I₂₂ = – (1 – P) log (1 – P);

.

Вводя обозначение (U, П) = и определяя коэффициент надёжности бинарной системы передачи дискретных сообщений как χ(U, П) = (U, П) / (U) ≡ χ(P, p, q) в случае а) получим:

(U, П) = (U), χ(P, 1, 1) = 1.

Удельная информативность (U, П) множества символов W на выходе канала КПДС при данном источнике ДИС U на его входе равна:

(U, П) = = ,

или (U, П) = . (7.1)

Величину R ≡ (U, П) К. Шеннон назвал «скоростью передачи информации» по каналу КПДС ([46], с. 277).

Мы будем под величиной (U, П) подразумевать среднее количество синтактической информации, передаваемой по каналу КПДС, на вход которого поступают всевозможные элементарные сообщения (знаки) uj U источника ДИС, а на выходе появляются символы (вторичные знаки) wk из совокупности W, приходящейся на один знак из совокупности U(бит/знак), поскольку рассматриваются статические системы ССПИ

В варианте а) на рис. 6:

(U, П) = – P log P – (1 – P ) log (1 – P ) = (U) [бит/знак].

В общем случае (N ≥ 2) при P_{j k} = δ_{j k} получаем:

I_{k j} = – δ _{j k} log P_j = – δ _{j k} log (P'_k /P_{j k}) и (U, П) = (U).

В случае б ) на рис. 6: p = q = 0, p + q = 0. Тогда P₁₁ = P₂₂ = 0, то есть переданному знаку u₁ никогда не будет соответствовать выходной символ w₁, а знаку u₂ – символ w₂. Однако это не значит, что информация в такой системе ССПИ будет полностью потеряна. Напротив, если декодер символу w₁ будет присваивать значение знака u₂, а символу w₂ – знака u₁ (согласно правилу максимума апостериорной вероятности), то потери информации в канале КПДС вообще не будет происходить и

(U, П) = = – (1 – P ) log (1 – P ) – P log P = (U).

В случае в) на рис. 6: p = 0, q = 1, p + q = 1. Очевидно, что здесь происходит полная потеря информации при любом алгоритме работы декодера, хотя

величина q ≠ 0.

Действительно. Вычислим значение функции (U, П).

Заметим, что P'₁ = 0, а P'₂ = 1. Значит:

j = 1, k = 1 ► P_j P_jk = P₁ P₁₁ = P · 0 = 0; j = 1, k = 2 ► P₁ P₁₁ = P₁· 1 = P;

j = 2, k = 1 ► P₂ P₂₁ = (1 – P )·0 = 0; j = 2, k = 2 ► P₂ P₂₂ = 1 – P;

(U, П) = 0 – P log 1 + 0 – (1 – P ) log 1 = 0.

Если отнести величину (U, П) к удельной информативности (U) источника ДИС, то в случаях а) ( p + q = 2) и б ) ( p + q = 0) получим: χ(P, p, q) = = (U, П)/ (U) = 1, а в случае в): p = 0, q = 1, p + q= 1, χ( P, 0, 1) = 0.

Величина κ (P, p, q) = 1 – χ (P, p, q) показывает процент потерь информации источника ДИС в канале КПДС; поэтому величину χ (P, p, q) = 1 – κ (P, p, q) следует называтькоэффициентом информационной надёжности статической системы передачи дискретных сообщений (ССПИ ).

В случае г) на рис. 6 ( p = q = 1/2) получаем следующее:

P'₁ = (P + 1 – P) = = P'₂;

P₁ P₁₁ I₁₁ = – P log = 0; P₁ P₁₂ I₂₁ = 0;

P₂ P₂₁ I₁₂ = P₂ P₂₂ I₂₂ = 0; (U, П) = 0; χ(P, , ) = 0,

то есть в этом случае в канале КПДС также происходит полная потеря информации относительно любой достаточно длинной входной последовательности S_i⁽ⁿ⁾ = ( u_i1, u_i2, …, u_ik, …, u_in ), n >> 1.

Рассмотрим общий случай (0 < p < 1, 0 < q < 1) и определим, когда происходит полная потеря информации в системе ССПИ. Теперь уже совершенно ясно, что это произойдёт в случае, если вероятность поступления к получателю ПИ символа w_k не зависит от того, какой из знаков u_j множества U = {u_j} был выдан источником ДИС в канал КПДС, то есть при P (w_k|u_j) = P (w_k).

При k = 1, j = 1: P(w₁) = P'₁ = P(w₁|u₁) = p.

При k = 1, j = 2: P(w₁) = P'₁ = P(w₁|u₂) = 1 – q.

Приравнивая правые части этих равенств, получаем:

p = 1 – q, или p + q = 1, а χ(P, p, q) = 0.

То же самое получается при k = 2. Частные случаи ( p = 0, q = 1: случай в) и p = q = 0,5: случай г) на рис. 6) как раз соответствуют варианту p + q = 1.

Итак,если p + q = 2, то (U, П) = (U), χ(P, p, q) = 1;

если p + q = 0, то (U, П) = (U), χ(P, p, q) = 1;

если p + q = 1, то (U, П) = 0, и надёжность канала КПДС становится нулевой: χ(P, p, q) = 0.

Значит, мы получили два сечения поверхности χ(P, p, q) по уровням χ = 1 и χ = 0 (см. рис. 7): точки (0, 0, 1) и (1, 1, 1), в которых χ(P, p, q) = 1, и прямую p + q = 1 на плоскости ( p, q), на которой χ(P, p, q) = 0.

Рис. 7. Зависимость коэффициента информационной надёжности χ

канала КПДС от величин p и q

Если p + q ≠ 2, p + q ≠ 0, а также p + q ≠ 1, то 0 < χ(P, p, q) < 1, и эти две точки и прямую можно соединить, при заданном значении P и различных зна-

чениях p и q, непрерывной поверхностью χ(P, p, q) по формуле:

χ(P, p, q) = / (U), (7.2)

где P'_k = , а (U) = – P log P – (1 – P) log (1 – P).

Зависимость коэффициента надёжности χ(P, p, q) бинарной статической системы передачи семиотической («дискретной») информации ССПИ от переменных p и q при P = 0,5 представлена на рис. 7.

Отметим, что в симметричных бинарных системах ССПИ( p = q) непреднамеренные помехи (естественного и искусственного происхождения) могут снизить величину ( p + q) от значения p + q = 2 ( p = q = 1) до значения p + q = 1 (то есть p = q = 0,5: см. рис. 7). Интервал значений от p + q = 0 ( p = q = 0) до p + q = 1 относится к организованным «противником» помехам в канале КПДС.

Пусть в качестве знаков u₁ и символов w₁ используется “1”, а в качестве u₂ и w₂ – “0” (современные бинарные цифровые системы электросвязи). Если «противник» – глупый, то он каждую посланную источником ДИС “единицу” будет ретранслировать как “ноль” и наоборот. Нетрудно распознать такой алгоритм подавления электросвязи и поменять алгоритм работы сканера: “единицам” первичного источника ДИС присваивать значения символов “ноль” и наоборот. В таком случае эффективность противодействия «глупого противника» становится нулевой, а канал передачи информации – стопроцентно надёжным.

Для распознавания субъектами общения такого «глупого противника» им достаточно договориться, что вместе с информационным блоком всегда будет передаваться известная источнику ДИС и получателю ПИ псевдослучайная последовательность, анализ которой и выявит тактику «противника».

В сотовых системах стандарта GSM 900 такая псевдослучайная последовательность служит для оценки текущей надёжности канала КПДС в каждом рабочем кадре (так называемая «обучающая последовательность»).

Максимальная эффективность противодействия обмену информацией между ДИС и ПИ будет иметь место при p + q = 1; например, когда «противник» половину “единиц” будет ретранслировать, по псевдослучайному закону, как “ноли”, а половину “нолей” – как “единицы”.

В этом случае p = q = 0,5 и χ(P, p, q) = 0.

Мы так подробно остановились на вопросе о потере знаковой («дискретной») информации в каналах КПДС при наличии в них непреднамеренных или организованных помех потому, что его решение наиболее трудно для понимания, а в соответствующей литературе по этому вопросу наблюдаются разночтения. В то же время, адекватное решение вопроса о потерях информации в каналах связи и правильная его ( решения) интерпретация имеют фундаментальное значение для понимания прикладной теории информации и её приложений.