7. Потери информации в системах электросвязи при наличии помех Пятый постулат теории информации

Вернёмся к рис. 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_jU, либо всем им будет соответствовать выходной символ w_k.

Каким же образом символу w_kW на выходе КПДС следует присваивать значение некоторого знака u_jU? Оптимальным решением, с точки зрения математической статистики, будет следующее: символу 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.

Значит,

величиной I_{k j} = log (P_{j k} /P'_k) можно характеризовать

количество информации, содержащейся в выходном символе w_kW

относительно входного знака u_jU.

Если при всех значениях 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, П) подразумевать среднее количество

синтактической информации, передаваемой по каналу КПДС,

на вход которого поступают всевозможные элементарные

сообщения (знаки) u_j U источника ДИС, а на выходе появляются

символы (вторичные знаки) w_k из совокупности 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.

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

Рассмотрим эти решения и некоторые их интерпретации.

Итак, пусть количество информации I_{k j}, содержащейся в символе w_k W на выходе канала КПДС относительно выданного источником ДИС знака u_j U,

определяется формулой:

I_{k j} = log=. (7.3)

Поскольку формально-математически выражение (7.3) ниоткуда не следует, то соотношение (7.3) нужно рассматривать как пятый постулат теории информации.

А уже из этого постулата следует:

среднее на один знак u_jU количество информации (U, П),

получаемое на выходе статического канала КПДС,

относительно информации, выдаваемой источником ДИС, есть:

(U, П) = =log. (7.4)

При P_{j k} = δ_{j k} величина

(U, П) = log== (U, П).

Надёжность передачи информации по данному каналу КПДС от данного источника ДИС определяется коэффициентом информационной надёжности такой системы передачи дискретной информации ССПИ:

χ(U, П) = (U, П)/(U). (7.5)

Максимальная надёжность по всевозможным источникам ДИС определяется только переходной матрицей П = || P_jk || = || P(w_k|u_j); j, k, = 1, 2, …, N || и является собственной характеристикой информационной надёжности канала КПДС χ(П).

Если же пятый постулат теории информации (7.3) сформулировать непротиворечивым образом как-либо иначе, то, аналогично неевклидовым геометриям, можно получить столь же строгую «не-шенноновскую» теорию информации, применимость которой в данной научной области потребует дополнительных исследований.

Вопросы для самопроверки

1. Что такое переходная матрица системы электросвязи и в чём состоит математический смысл её элементов?

2. Какова обобщённая структура статической системы передачи дискретных сообщений при наличии в ней помех?

3. При каких условиях происходит полная потеря информации в бинарных дискретных системах передачи информации?

4. Какова общая зависимость коэффициента информационной надёжности бинарного канала передачи дискретных сообщений от величины элементов его переходной матрицы?

5. В чём состоит пятый постулат теории информации, и каков его математический смысл?

6. Каково среднее на один знак источника дискретных сообщений количество информации, получаемое на выходе канала передачи дискретных сообщений?

7. Как определяется коэффициент информационной надёжности системы передачи дискретных сообщений при наличии помех в её канале связи?