В отсутствие помех

Рассмотрим вопросы, связанные с передачей информации встатических знаковых («дискретных») информационных системах,на примере функционирования системы передачи дискретных сообщений типа «ДИС–кодер–посто-янное запоминающее устройство (ПЗУ)–сканер–линия связи–декодер–ПИ» (см. рис. 4). Для конкретности будем подразумевать под такой системой электронную почту. Пользователь персонального компьютера с помощью клавиатуры ПК набирает текст, который кодируется и помещается в ПЗУ. По команде пользователя текст отправляется по кабелю на сервер (ПЗУ). Адресат-ПИ обращается в свой «почтовый ящик», анализирует почту и нужные письма сканирует. По линии связи они поступают на ПК адресата и декодируются. Фактор времени как таковой здесь отсутствует; поэтому такую систему можно считать статической.

U = { u_j } u₁ ○ π₁₁ = 1 ○ w₁ W = {w_k}

P = { P_j } u₂ ○ ○ w₂ P_вых = {P'_k}

I = { I_j } u_j ○ ○ w_k I_вых ={I'_{k j}; i, k = 1, 2, …, N }

H(U) = – u_N ○ π_N1 = 1 π_2N = 1 ○ w_N

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

знаковой (дискретной) информации без помех

Пусть источник ДИС выдаёт некоторое сложное знаковое сообщение (текст) S_i⁽ⁿ⁾ = ( u_i1, u_i2, …, u_il, …, u_in ), которое посредством входного преобразователя (на рис. 4 не показан) записывается с помощью некоторого множества символов в ПЗУ. Через некоторое время (по запросу получателя информации ПИ или по расписанию) сканер считывает из ПЗУ это сообщение, это сообщение передаётся по линии связи, декодируется и посредством выходного преобразователя (на рис. 4 не показан) предоставляется получателю ПИ в виде последовательности символов S'_i⁽ⁿ⁾ = (w_i1, w_i2, …, w_il, …, w_in). Функционирующую таким образом информационную систему будем называть статической системой передачи информации (ССПИ).

Знаки {u_j} и символы {w_k} могут иметьразличную физическую реализацию. Например, знакам {u_j} могут соответствовать клавиши латинизированной клавиатуры компьютера, а символам {w_k} – изображения на мониторе

компьютера фигурки моряка-сигнальщика с соответствующими положениями рук и флажков (морской тренажёр для обучения семафорной азбуки). Или же: знакам {u_j} могут соответствовать фонемы обычной речи, а символам {w_k} – буквы алфавита данного языка (анализатор речи). Или же: знакам {u_j} могут соответствовать фонемы, а символам {w_k} – визуальные знаки азбуки глухонемых и т. п.

В последнем случае анализатор речи записывает поступившее от микрофона сообщение, распознаёт фонемы {u_j} и записывает речевое сообщение в ПЗУ с помощью символов {w_k} , обозначающих буквы данного языка. При считывании информации символы {w_k} превращаются в знаки азбуки глухонемых, которые и отображаются на дисплее монитора. При этом количество фонем {u_j} в сообщении (фразе) S_i⁽ⁿ⁾ = ( u_i1, u_i2, …, u_il, …, u_in ) может не совпадать с количеством символов {w_k} , что может привести к потере информации в системе ССПИ. Например, в слове «солнце» пять фонем из множества {u_j} : с-о-н-ц-е. Однако оно записывается с помощью шести символов {w_k} : с-о-л-н-ц-е. В силу смысловой избыточности русского языка в этом случае потери информации в системе ССПИ не произойдёт. С другой стороны, очень часто из русского языка пытаются «изгнать» букву «ё». Поэтому синтезатор речи вместо слова «съём» (квартиры) синтезирует слово «съем», вместо «вёдро» (о погоде) – «ведрó», вместо «осёл» – «осéл» и т. п. Или: как правильно запрограммировать синтезатор, если в тексте есть фразы «все равно» и «все равны»? Как нужно понимать первую фразу: то ли как «всё равно», то ли считать, что в ней допущена ошибка и её следует синтезировать как «все равны»?

Значит, даже в отсутствие помех в канале КПДС при работе системы ССПИ может происходить потеря синтактической («перепутывание знаков»), а значит и семантической информации.

Как можно оценить потери информации в таких системах ССПИматематически? Для простоты будем считать, что количество знаков {u_j} на входе канала КПДС и символов {w_k} на его выходе одно и то же – N (вообще говоря – это не обязательно!).

В разд. 3 мы установили, что простейший источник ДИС можно характеризовать тремя множествами: множеством первичных знаков U = {u_j} , множеством вероятностей P = {P_j} независимого появления знаков u_j в произвольной последовательности S_i⁽ⁿ⁾ (P_j = P(u_j) – априорные, по отношению к каналу КПДС, вероятности) и информационным множеством I = {I_j} ; I_j = – log P_j.

На выходе канала КПДС могут появляться любые символы w_k из множества W = {w_k} . Вероятности их появления P'_k (вообще говоря, P'_k ≠ P_j) образуют множество выходных вероятностей P_вых = {P'_k} . Каждый из символов w_k W может нести некоторое количество информации I_{k j}, (k, j = 1, 2, …, N ), содержащейся во входных элементарных сообщениях (знаках) u_j U. Каждому символу w_k W по определённому правилу ( распознавания символов) ставится в соответствие один, и только один из знаков u_j U (символу w_k присваивается значение знака u_j ). Субъект-ПИ знает это правило и соответствующим образом воспринимает полученное сообщение.

Поскольку количество знаков {u_j} и символов {w_k} одинаково и равно N, то канал КПДС можно охарактеризовать квадратной матрицей соответствия Π = || π_jk; j, k = 1, 2, …, N || порядка N, в каждой строке которой стоит одна единица и (N – 1) нолей. Если записать алфавит {u_j} в виде вектора-строки u^Т = || u₁, u₂, …, u_j, …, u_N || и аналогично совокупность {w_k} выходных символов в виде w^Т = ||w₁, w₂, …, w_k, …, u_N ||, то функционирование системы ССПИ математически может быть представлено как u^Т Π = w^Т, или w = Π^Т u. При этом сообщению (u_j + u_l) соответствует событие u_j U u_l.

Если матрица Π – диагональная (Π = || δ_jk; j, k = 1, 2, …, N ||, где δ_jk – символ Кронекера: δ_jk = 1 при j = k и δ_jk = 0 при j ≠ k), то каждому знаку u_j будет соответствовать один, и только один символ w_j – и никакой потери синтактической информации в канале КПДС происходить не будет, поскольку в этом случае по формуле полной вероятности , и в этом случае выход канала КПДС являетсявторичным источником ДИСс характеристиками:

P'_k = P_k, P'_j = P_j, I_{k j} = – δ_jk log P_k = – δ_{k j} log P_j = – log P_k = I_k = I_j.

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

(U, П) = ,

или (U, П) = = H(U) (бит/знак). (6.1)

Если матрица Π – диагонализируемая, то есть если она может быть приведена, за счёт перестановки столбцов, к диагональному виду, то потери информации в канале КПДС с матрицей соответствия П происходить также не будет. Просто каждому w_k (k = 1, 2, …, N ) будет присваиваться значение одного, и только одного знака u_j в соответствии со структурой матрицы П.

Например, матрица соответствия П= – диагонализируемая, и на выходе канала КПДС символу w₁ будет присваиваться значение знака u₂,

w₂ → u₃ и w₃ → u₁.

А вот матрица П= – не диагонализируема, и на выходе соответствующего матрице П канала КПДС символу w₁ будет присваиваться значе-

ние знака u₁ – с вероятностью P₁, символу w₃: значение u₂ – с вероятностью P₂ и значение u₃ с вероятностью P₃, а символ w₃ на выходе КПДС не появится никогда. Поэтому в таком канале КПДС будет происходить частичная потеря информации относительно информации источника ДИС.

Можно ли узнать заранее, по виду матрица П, диагонализируема она или же нет? И если нет, то, какое количество синтактической информации теряется в канале КПДС при данном источнике ДИС? И у какого из источников ДИС потери информации будут наименьшими?

На первый вопрос можно ответить, просмотрев все столбцы матрицы П. На ЦВМ это можно сделать автоматически. У диагональной матрицы Π = || δ_jk; j, k = 1, 2, …, N || определитель (детерминант) равен единице: det Π = 1. Поскольку для любой квадратной матрицы A перестановка столбцов (или строк) не приводит к изменению модуля её детерминанта, то матрица Π будет диагонализируемой, если | det Π | = 1.

Если det Π = 0, то матрица Π – не диагонализируема, и в соответствующем ей канале КПДС будет происходить потеря информации. В таком случае нам нужно знать, какой процент потерь информации произойдёт в канале КПДС в среднем на один знак данного источника ДИС (то есть информационную надёжность данной системы ССПИ ).

Ясно, что если при данных значениях j и k символу w_k приписывается значение знака u_j (то есть π_jk = 1) и это соответствие одно-однозначное (то есть иных значений у символа w_k не бывает), то P(w_k) = P(u_j), или P'_k = P_j, и количество информации I_{k j}, содержащейся в символе w_k относительно знака u_j, равно

I_{k j} = – log P_j = log (π _{j k} /P'_k).

Если π_jk = 0, то будем считать, что количество информации I_{k j}, содержа-

щейся в символе w_k относительно знака u_j, равно нулю, поскольку в среднем

π _{j k} log (π _{j k} /P'_k) = 0.

Если же π _{j k} = 1 и P'_k ≠ P_j, то по формуле полной вероятности

P'_k ≡ P(w_k) = = > P_j,

где в суммировании по индексу l участвуют только те из величин π_jk столбца k

матрицы соответствия Π, значения которых равны единице.

Поскольку все значения P_l (как вероятности) в сумме – положительны, то 0 < P_l < (P'_k = ) < 1.

Значит, в этом случае выполняется строгое неравенство

0 < < – log P_j < ∞,

или 0 < I_{k j} < I_j < ∞, то есть в символе w_k, соответствующему условию π _jk = 1 и P'_k ≠ P_j, содержится меньшее количество информации, чем в знаке u_j.

Таким образом,

в качестве меры количества информации, которая содержится в выходном символе wk относительно входного знака uj источника ДИС U = {uj} на выходе статического канала КПДС с матрицей соответствия Π можно полагать величину Ik j = π j k log (π j k /P'k), где P'k = .

Среднее количество информации, содержащейся в совокупности W всех выходных символов w_k (k = 1, 2, …, N ) относительно некоторого входного зна-

ка u_j, есть

.

Среднее количество информации, которое получает субъект-ПИ на выходе канала КПДС системы ССПИ, приходящейся на любой из знаков u_j U ис-

точника ДИС:

(бит/знак). (6.2)

Безразмерный коэффициент информационной надёжности системы ССПИ зависит как от информационных характеристик входного источника ДИС {U, P, I, S}, так и от характеристик канала КПДС {W, Π}.

Можно поставить вопрос: каково же максимальное по всевозможным источникам ДИС значение коэффициента надёжности ? Это значение можно назвать коэффициентом надёжности данного канала КПДС, поскольку он определяется только структурой матрицы соответствия Π.

Для ответа на поставленный вопрос заметим, что формула (6.2) определяет среднее количество информации, получаемое на выходе канала КПДС при подключении на его вход данного источника ДИС U, которое приходится на один знак из совокупности U= {u_j} . Значит, соответствующими численными методами линейного программирования можно найти такой источник ДИС (то есть имеющий такие значения P₁, P₂, …, P_j, …, P_N при условии ), который реализует максимальное значение величины . Мы не будем входить в детали решения такой задачи, а проиллюстрируем вычисление коэффициента надёжности на простейшем примере.

Рассчитаем среднее количество информации на выходе системы ССПИ, имеющей в качестве источника ДИС совокупность характеристик

U = {u₁, u₂, u₃}; P = {1/3, 1/3, 1/3}; I = {log 3, log 3, log 3};

≈ 1,6 (бит/знак),

а в качестве канала КПДС – канал с недиагонализируемой матрицей соответствия (см. предыдущие примеры) П= .

В этом случае: P'₁ = P₁ = 1/3, P'₂ = 0, P'₃ = 1/3 + 1/3 = 2/3, и с вероятностью P₁ = 1/3 мы будем получать соответствие символа w₁ знаку u₁, то есть I₁₁ = log 3; с вероятностью P₂ = 1/3 – соответствие символа w₃ знаку u₂, то есть I₃₂ = log (3/2), и с вероятностью P₃ = 1/3 – значение u₃, то есть I₃₃ = log (3/2).

Среднее на один знак алфавита U количество информации на выходе системы ССПИ есть: (бит/знак), то есть потери информации в такой системе составляют около 0,87 бит-на-знак алфавита U, акоэффициент информационной надёжностиχ(U, П) ≈ 0,45.

Значит, в рассмотренном канале КПДС теряется около 55 % информации.

Если же к каналу КПДС подключить источник ДИС с характеристиками

P = { , , }, I = {1, 2, 2}, ,

то этот источник можно закодировать с помощью множества промежуточных символов V = {v₁, v₂} таким образом (алгоритм Шеннона-Фано):

u₁ → v₁; u₂ → (v₂, v₁); u₃ → (v₂, v₂).

Если подавать эти равновероятные символы v₁ и v₂ в канал КПДС с матрицей соответствия Π рассмотренной нами системы ССПИ, то получим следующее: символу w₁ с вероятностью 0,5 будет присваиваться значение промежуточного символа v₁, а символу w₃ с вероятностью 0,5 значение v₃. В такой системе ССПИ потерь синтактической информации не будет, источник ДИС за счёт соответствующего кодера будет согласован с каналом КПДС, имеющим данную матрицу соответствия Π, а канал КПДС может обслуживать различные источники ДИС U = {u₁, u₂, u₃}, у которых алфавит содержит только три первичных знака и обладает удельной информативностью не более 1,5 бит/знак.

Практически более интересно рассмотреть такие каналы КПДС с диагонализируемыми матрицами соответствия Π, в которых потери информации происходят не за счёт «неправильного» построения алгоритма распознавания знаков u_j, а за счёт различных помех, которые воздействуют на канал КПДС системы ССПИ. Этот вопрос мы рассмотрим в разд. 7.

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

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

2. Что такое матрица соответствия и что она характеризует?

3. Что такое диагонализируемая матрица соответствия и каков её смысл?

4. Как проверить диагонализируемость матрицы соответствия?

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