Пшеницын В.И.

Санкт-петербургский государственный университет водных коммуникаций

Мульганов С.В.

Санкт-петербургский государственный университет водных коммуникаций

 

потери информации при передаче цифровых сигналов при наличии окон замирания

 

Хорошо известно, что при расчете пропускной способности канала связи всякий перерыв в приеме сигнала вызывает, вообще говоря, потерю части полезной информации. В количественном смысле такую потерю можно оценивать, сравнивая энтропию исходного сигнала S(A) с энтропией сигнала после «вырезания» окон пропускания S(B). Такие окна могут иметь естественное происхождение (например, грозовые разряды), но могут носить и производственный характер. Разность S(A)-S(B), в отсутствии подключения посторонней информации, определяет величину потерянной информации. Для соответствующей оценки приведем сравнительно простой пример в условиях, когда исходный сигнал представляет собой не просто набор независимых импульсов (тогда они безвозвратно терялись бы в окне пропускания), а цепь Маркова, в которой из взаимной зависимости импульсов возможно частичное восстановление последних. Зависимость импульсов в цепи Маркова – один из факторов информационной безопасности.

Передаваемые для различных цепей длительные сигналы часто можно рассматривать как стационарные случайные процессы. В дальнейшем мы будем постоянно подразумевать дискретное время и какое-либо раз и навсегда заданное конечное множество состояний. При таких условиях, как известно [1], для заданного процесса А существует как энтропия Sn{A}его отрезка из n звеньев, так и предел в виде удельной энтропии:

.                                                                                (1)

Данная статья посвящена такой схеме передачи А как сигнала, при которой он не проходит в первоначальной форме, а вместо этого отдельные участки целиком выпадают. Мы останавливаемся на частной схеме, когда чередуются участки из l звеньев, не подверженные искажениям, с участками из m звеньев, полностью теряющимися (можно, например, представлять, что все эти звенья заменяются нулями). Например, при l=4, m=2 получается схема, изображенная на рис. 1.

Рис. 1. Схематическое изображение входного сигнала.

Для полученного сигнала с пропусканиями, обозначаемого как В, также можно определить энтропию Sn{В} достаточно длительного отрезка и удельную энтропию

.                                                                                (2)

Очевидно, процесс В получается детерминированным функциональным преобразованием. В таких случаях всегда

Sn{В} ≤ Sn{A}                                                                                   (3)

и в пределе

.                                                                                               (3а)

Разность

                                                                                         (4)

естественно трактовать как информацию, потерянную при переходе от А к В, также в расчете на одно звено. Вообще говоря , кроме вырожденных ситуаций с  , которые мы оставляем в стороне.

Что касается величины , то она может обращаться в нуль при достаточно естественных условиях, например, когда в А каждый символ повторяется дважды, причем m=1, тогда, как легко видеть, никакая информация не теряется и

.                                                                                               (5)

Другой простой пример получается при взаимной независимости всех звеньев А, из-за которой и передача информации происходит раздельно на каждом шаге, отчего при больших n

                                                                       (6)

                                                                                     (6а)

и

.                                                                                   (7)

Предположительно, формула (7) справедлива и при наличии корреляции в исходном процессе А. Во всяком случае, в ниже следующем примере это предположение оправдывается.

Как мы увидим ниже, случаи (5) и (7) задают границы, между которыми всегда располагается истинная удельная потеря информации. Рассмотрим чуть более сложный частный пример:

пусть процесс А, кроме стационарности, обладает еще и свойством марковости, а число состояний равно 2. Приписываем им номера 0 и 1, а условные вероятности перехода пусть будут

                                                                                (8)

с заданным постоянным . Данный процесс часто встречается как простейший пример цепи Маркова, соответствующие стационарные вероятности для него хорошо известны [1]:

                                                                                       (9)

Для подсчета нужных нам величин энтропии обозначим произвольный прошедший отрезок А как

                                                                                     (10)

Случайные величины xk (1 ≤ k ≤ l), принимающие значения 0 и 1, взаимозависимы, но их можно преобразовать к независимости [2], полагая

, k = 2, 3, …, l,                                                           (11)

где  – знак сложения по модулю 2, а hk – вспомогательные логические переменные, у которых hk=0, если между звеньями t=k-1 и t=k данной цепи Маркова происходит переход  или  и hk=0 в противном случае. Тогда h2…hl независимы друг от друга, и энтропия, как всегда при взаимно однозначном преобразовании дискретных величин, сохраняется при переходе от (10) к модифицированному отрезку

(x1, h2, …, hl),                                                                                  (12)

для которого энтропия определяется [1] прямым суммированием по всем звеньям. В итоге

                                               (13)

Если же мы сразу возьмем отрезок длины

   ,                                                                  (14)

то аналогично (13) находим

.                                     (15)

Обратимся теперь к следующему прошедшему отрезку

                                                                                  (16)

Для обеспечения независимости от (10), заменяем отрезок на

                                                                    (17)

где переменная  подбирается так, что бы быть независимой от последнего члена отрезка (10), чего, по свойству марковости, для нашей цепи достаточно. Отличие от построения величин h2 и т.д. состоит лишь в том, что место параметра a занимает  a’ — вероятность перехода в первоначальной цепи А из состояния 0 в состояние 1 или обратно за m +1 шагов. Для соответствующего расчета временно отмечаем индексом зависимость a’ от m. Тогда, в частности,

,                                                                                             (18)

а далее получаются типичные для цепей Маркова уравнения

                                                          (19)

С эквивалентным в данном случае

                                    (20)

и с начальными условиями (17) решением является (снова опускаем индекс)

                                                                          (21)

и попутно

.                                                                    (21а)

Распределение же случайных величин hl+m+2 и т.д. такое же, как у h2. Энтропия всего изучаемого отрезка процесса В теперь получается сложением:

       (22)

Для определения  остается только вычесть одну величину из другой (15) и (22), разделить на длину первоначального соотношения ­­n с учетом (14) и перейти к пределу , отбрасывая некоторые возникающие бесконечно малые члены. Остается

.            (23)

Из формулы (23) вытекает неравенство , поскольку из определения a (21) следует, что a’ ближе к среднему значению вероятности (1/2), чем a.

По своему смыслу, правая часть (23) положительна. Это не видно при непосредственном взгляде на формулу, но подтверждается как численно (рис. 2), так и специальными выкладками.

 

0,1
 

0,2
 

l=16
 

a
 

Рис. 2. Зависимость удельных потерь информации от длин интервалов замирания и от вероятности перехода из одного состояния в другое.

Из рис. 2 видно, что потери информации растут с увеличением длины участка замирания при фиксированной длине участка пропускания.

Отметим еще свойство симметрии: в нашем примере величина  не меняется от замены  (хотя сами процессы А и В становятся несколько иными). Это следует из формулы выражения (23) с учетом того, что согласно (21) и (21а) при указанной замене либо a’ сохраняет свое значение (при нечетном m), либо происходит перестановка  (при четном m).

Из полученного соотношения (23) и неравенства (3) вытекает общая закономерность:  — доля потерянной информации из стационарного процесса с произвольной корреляцией его звеньев не превышает доли времени с замираниями. Этот вывод верен лишь асимптотически для длинных сигналов, и во всей статье предполагается отсутствие налагающихся помех, иначе исходное соотношение (4) становится несправедливым.

 

Литература:

1.                             Стратонович Р.Л. Теория информации. М. Сов. радио, 1975.

2.                             Карлин С. Основы теории случайных процессов. Мир, М, 1971, 536 с.