Файл: прикладная теория информации.pdf

1.2. Эталонная модель взаимосвязи открытых систем
Для построения надежных и эффективных информационных систем для каналов с различной средой, разным отношением сигнал/шум необходимо ис- пользовать и другие (дополнительные) модели. Наиболее известна так называе- мая эталонная модель взаимосвязи открытых систем, где в обобщенном виде рас- смотрены функции системы выполняемые на различных уровнях. Модель пред- ставляет семиуровневую архитектуру:
1. На физическом уровне реализуется канал.
2. На канальном уровне реализуется процедуры эффективного кодирова- ния (сжатия), шифрования, помехоустойчивому кодирования информации.
3. На сетевом уровне реализуется передача информации от источника к ад- ресату.
4. Транспортный уровень управляет сквозной передачей пакетов с коррек- цией ошибок.
5. Сеансовый уровень контролирует соединения между оконечными систе- мами.
6. На уровне представления выполняются операции сжатия данных, за- щиты информации, преобразования форматов для обеспечения эффективного и безопасного взаимодействия.
7. Прикладной уровень предоставляет различные сетевые службы.
1.3. Первичное кодирование информации
Дискретный поток двоичных символов, сформированный аналого-цифро- вым преобразователем (АЦП – как простейший первичный кодер) представля- ется в виде обычного двоичного кода. Такой код записывается последовательно- стью единиц „1“ и нулей „0“. В реальных каналах передачи информации, из-за недопустимых частотных, амплитудных, помеховых и др. искажений, простой двоичный код часто оказывается непригодным для передачи, хранения и обра- ботки информации. Поэтому двоичный код, как правило, преобразуется в дру- гую форму первичного кодирования, наиблее подходящую для конкретных при- менений. Кроме того, в современных цифровых измерительных приборах, например, вольтметрах, частотометрах, спектроанализаторах и др., с точки зре- ния удобства восприятия измеряемых параметров, используется десятичное

12 представление данных. В таких приборах используются 7-сегментные индика- торы при вводе и выводе буквенно-цифровых данных. В этом случае требуется промежуточное преобразование простого двоичного кода в некоторое другое отображение – первичное кодирование информации. Кратко рассмотрим некото- рые первичные коды.
Весовые коды. Первичное кодирование может осуществляться посред- ством весовых кодов.
Как известно, любое n-разрядное число N с основанием q представляется многочленом вида
???? = ∑
????
????
????
????=0
????
????
= ????
0
????
0
+ ????
1
????
1
+ ⋯ + ????
????
????
????
, где ????
????
– значение разрядного коэффициента i- го разряда.
Для двоичного весового кода основание ???? = 2, ????
????
∈ {0,1}, Например, десятич- ное число 13 записывается как
13 = 1 × 2 3
+ 1 × 2 2
+ 0 × 2 1
+ 1 × 2 0
В примере веса – это величины, равные степени по основанию два, на ко- торые умножаются разрядные коэффициенты или по другому – двоичные цифры. На практике широко применяются весовые коды, которые используют двоичную, восьмеричную, десятичную и др. системы счисления.
Примером весового кода является двоично-десятичный код, где веса – это значения 8, 4, 2, 1. В двоично-десятичном коде каждая десятичная цифра зада- ется словом из 4 двоичных цифр. Например, число 127 записывается как
(000100100111).
В теории кодирования с целью удобства записи процесса кодирования и декодирования с помощью неприводимых полиномов над простым полем Галуа
GF(2) кода используется восьмеричная система счисления, где каждая восьме- ричная цифра (0, 1,...,7) представляется словом из трех двоичных символов.
Например, восьмеричное число 103 8
обозначает полином 6-степени. В двоичной записи этому числу соответствует 001000011. Двоичные символы являются ко- эффициентами полинома, и коэффициент старшей степени полинома располо- жен слева.
В общем случае любой полином над алгебраическим полем F записывается как
????(????) = ????
0
????
0
+ ????
1
????
1
+ ⋯ + ????
????−1
????
????−1
= ∑ ????
????
????−1
????=0
????
????
, где x – переменная над алгебраическим полем F. Значения ????
????
, … , ????
????−1
называ- ются коэффициентами над алгебраическим полем F.
Очевидно, записи 001000011 соответствует полином

13
????(????) = ????
6
+ ????
1
+ 1.
Названные коды применяются для кодирования команд, операндов и дру- гих данных, предназначенных для применения в цифровых системах, устрой- ствах, процессорах, компьютерах и пр.
Буквенно-цифровые коды. На этапе первичного кодирования использу- ются и буквенно-цифровые коды. Кроме двоичного кодирования десятичных цифр, буквенно-цифровые коды позволяют получить двоичное изображение тек- стовых символов, чисел, знаков препинания и управляющих символов. Одним из таких кодов является ASCII-код (American Standard Code for Information
Interchange – Американский стандартный код для обмена информацией) – это сравнительно давно принятый стандарт для представления данных в цифровой форме. Каждый символ обозначается числом от 32 до 127. Используется семь чипов для идентификации символа и один чип добавляется таким образом, чтобы количество единиц в кодовом слове было четным. Получается блоковый равно- мерный код с контролем четности длиной 8 бит (1 байт). Например, символу DEL соответствует кодовое слово (1 1 1 1 1 1 1 1). Символ $ кодируется словом ASCII- кода как (0 0 1 0 0 1 0 0).
1.3.1. Рефлексные коды
В двоичном коде при переходе от кодирования одного десятичного числа к другому может происходить одновременное изменение двоичных цифр в не- скольких разрядах. Например, при переходе от изображения числа 15 → 01111к числу 16 →10000 одновременно изменяются цифры в пяти разрядах. Это может являтся источником ошибок при кодировании информации. Эффективным сред- ством борьбы с ошибкой неоднозначности считывания является использование рефлексных кодов (отраженных кодов). Типичным представителем таких кодов является код Грея.
Код Грея. Основным свойством кода Грея является то, что любые два со- седние кодовые слова различаются только в одном разряде. На рис. 1.2. показаны соответствия между десятичным числом, простым двоичным кодом и двоичным кодом Грея.

14
[
0 1
2 3
4 5
6 7
8]
→
[
0 0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
0 0 0]
→
[
0 0 0 0
0 0 0 1
0 0 1 1
0 0 1 0
0 1 1 0
0 1 1 1
0 1 0 1
0 1 0 0
1 1 0 0]
Рис. 1.2. Код Грея
Например, пусть последовательно считываются числа 4 и 5. Им соответ- ствуют слова кода Грея (0 1 1 0) и (0 1 1 1). Прием же после числа 4 → (0 1 1 0) слова (1 1 1 1) с отличием в двух двоичных символах, свидетельствует о возник- шей ошибке.

15
2. КАЧЕСТВЕННАЯ И КОЛИЧЕСТВЕННАЯ ОЦЕНКА ИНФОРМАЦИИ
Под термином «информация» понимаются сведения, известия, которые описывают некоторое событие, руководство к действию или свойство какого- либо объекта. Эти сведения могут быть представлены определенными симво- лами, буквами алфавита, или в каком-то другом виде, например, изображением объекта «интереса», словами и пр. Формой представления информации является сообщение. В конкретных информационных системах сообщение может исполь- зоваться, передаваться, становиться объектом хранения, распределения, преоб- разования.
Н. Виннер (Norbert Wiener, амер. математик, философ, (1894-1964)) опре- делил информацию как объект нематериальной природы: «Информация есть ин- формация, а не материя или энергия». В основе теории информации лежит поло- жение о том, что любой источник информации можно описать вероятностными категориями, которые могут быть измерены. Каждое сообщение содержит в себе определенную информацию. Однако одни сообщения переносят больше инфор- мации, чем другие. Если в прогнозе погоды сообщается, что 1 января темпера- тура воздуха в Минске достигнет + 20 °С, то это сообщение характеризуется очень большим количеством информации. Такое событие является неожидан- ным, редким, вероятность ???? его появления стремится к нулю, ???? → 0. В сообще- нии, что 1 января температура воздуха в Минске ожидается – 5 °С не является неожиданным. Вероятность ???? его появления стремится к единице, ???? → 1. В со- общении о высоковероятностном событии содержится мало информации. Веро- ятность события является мерой его неожиданности (неопределенности) и свя- зана с количественной мерой информации. Можно предположить, что количе- ство информации о событии обратно величине вероятности его появления, т. е.
???? log
1
????
− log ????, (2.1) где ???? – количество информации, полученное с появлением сообщения с вероят- ностью ????.
Чтобы определить понятие количества информации, как измеряемой вели- чины, необходимо вначале рассмотреть свойства источника информации и канал передачи информации.
2.1. Дискретный источник информации без памяти
Дискретный источник информации без памяти ???? в дискретный момент времени ???? формирует символ ????
????
случайной последовательности символов. Выход источника есть случайная величина. Множество исходных символов ???? =
{????
1
, ????
2
, … , ????
????
} называется алфавитом источника ????, а элементы ????
????
– буквами или символами. Символами источника могут быть буквы, цифры или некие абстракт-

16 ные знаки. Каждый n-й символ из конечного алфавита ???? = {????
1
, ????
2
, … , ????
????
} источ- ника появляется на выходе с вероятностью ????
????
. Вероятности появления символов источника задаются в виде множества {????
1
, ????
2
, … , ????
????
}. Все вероятности символов в сумме должны давать значение 1, т. е.
∑
????
????
= 1
????
????=1
, где ???? – число различных символов множества, которое определяет размерность используемого алфавита.
Например, если ???? = {????
1
= ????, ????
2
= ????, ????
3
= ????}, ???? = {????, ????, ????}, ???? = 3, {????
1
=
=
1 2
, ????
2
=
1 3
, ????
3
=
1 6
}.
Алфавиту ???? = {0, 1}, ???? = 2, соответствует двоичный источник без памяти.
Выходными символами источника являются символы ????
1
= 0 и ????
2
= 1. Обозна- чим ????
1
вероятность появления символа
????
1
. Тогда выражение ????
2
= (1 − ????
1
) пред- ставляет вероятность появления символа ????
2
= 1.
Определение 2.1. Два источника ???? = {????
1
, ????
2
, … , ????
????
} и ???? = {????
1
, ????
2
, … , ????
????
} являются статистически независимыми, если вероятность ????
????
не зависит от того осуществились события ????
1
, ????
2
, … , ????
????
или нет.
Два источника
???? = {????
1
, ????
2
, … , ????
????
} и ???? = {????
1
, ????
2
, … , ????
????
} являются незави- симыми, если совместная вероятность ????
????,????
каждой пары
(????, ????) событий ???? ∈
????, ???? ∈ ???? равна произведению
????
????,????
= ????
????
????
????
, где ????
????
и
????
????
– вероятности появления символов источников
???? и ????.
Определение 2.1.1. Источник ???? = {????
1
, ????
2
, … , ????
????
} называется статистиче- ски зависимым от источника ???? = {????
1
, ????
2
, … , ????
????
}, если вероятность ????
????
зависит от того осуществились события ????
1
, ????
2
, … , ????
????
или нет.
В зависимом источнике событие ????
????
с вероятностью появления
????
????
изме- няет вероятность появления ????
????
события
????
????
2.1.1. Блоковый источник информации
Определение 2.2. Если выходом источника являются последовательности
(блоки) из ???? одиночных статистически независимых символов алфавита ???? =
{????
1
, ????
2
, … , ????
????
}, то такой источник называется источником с n -кратным расши- рением ????
????
источника
????.
На выходе блокового источника можно сформировать ????
????
символов.
Например, для ???? = {0, 1}, ???? = 2 множество символов источника с 2-кратным расширением источника ???? есть

17
????
2
= {????
1
, ????
2
, ????
3
, ????
4
}, где ????
1
= (00), ????
2
= (01), ????
3
= (10), ????
4
= (11) образуют множество, состоящее из ????
????
= 2 2
= 4-х символов блокового источника.
2.2. Канал передачи информации
Передача информации, формируемой источником, осуществляется по- средством использования канала передачи информации. Канал – это некоторая физическая среда, соединяющая источник информации с получателем. Примеры каналов: проводная телефонная линия; среда распространения электромагнит- ных волн (радиоканал), используемая, например, при соединении компьютера, имеющем Wi-Fi-адаптер, с сетью Internet. CD (компакт-диск) – это тоже канал в виде ЗУ и пр. На рис. 2.1. изображена обобщенная математическая модель си- стемы передачи информации, включающая канал.
Рис. 2.1. Модель системы передачи информации
Замечание. Эффективность каналов передачи (хранения) информации воз- растает с переходом на недвоичные символы.
2.3. Дискретный канал без памяти
Алфавиты передаваемых и принимаемых символов сообщения должны совпадать. Однако, из-за воздействия помех (шума) полученный символ может отличаться от переданного. В этом случае принимаемые символы называют ал- фавитом канала. На рис. 2.1 они обозначены как ???? = {????
1
, ????
2
, … , ????
????
} и приемник можно так же считать источником информации.
Каналы с шумами характеризуются условными вероятностями ????(????|????) для всех ???? ∈ ???? и ???? ∈ ????.
Определение 2.3. Условная вероятность ????(????|????) понимается как вероят- ность того, что на выходе канала (входе приемника) появился символ ????, при условии, что на выходе источника ???? был сформирован символ ????.
Источник ???? = {????
1
, ????
2
, … , ????
????
} статистически не зависит от источника ???? =
{????
1
, ????
2
, … , ????
????
}, если
????(????|????) = ????(????).

18
Напомним, если при вычислении вероятности ????(????) события ????
1
, ????
2
, … , ????
????
во внимание не принимаются, то вероятность называется безусловной.
Согласно определению (2.1.1) источник ???? = {????
1
, ????
2
, … , ????
????
} статистически зависит от источника ???? = {????
1
, ????
2
, … , ????
????
}, если
????(????|????) ≠ ????(????).
Замечание. Условные вероятности ????(????|????) называются вероятностями пе- рехода канала.
Определение 2.4. Если имеется конечное число входов и выходов канала, и принимается, что вероятность ????(????|????) не зависит от вероятностей появления предыдущих символов входа, то канал называется дискретным каналом без па- мяти.
Определение 2.4.1. Если шумы в канале являются случайными, то канал определяется как дискретный канал без памяти.
В ряде приложений, например, связанных с задачами обнаружения сигна- лов на фоне помех, условную вероятность ????(????|????) называют апостериорной (по- слеопытной) вероятностью.
Обратная условная вероятность канала ????(????|????) определяет вероятность приема символа ????, если на выходе канала имеется символ ????. Условная вероят- ность ????(????|????) позволяет оценить качество приема.
Дискретный канал с алфавитом символов источника (входом канала) ???? =
{????
1
, ????
2
, … , ????
????
} и символов источника (выходом канала) ???? = {????
1
, ????
2
, … , ????
????
} опи- сывается графом переходных вероятностей ????(????|????). На рис. 2.2 показано графи- ческое описание дискретного канала с двумя символами на входе и выходе ка- нала.
Рис. 2.2. Модель дискретного каналa передачи информации с набором вероятностей перехода

19
2.4. Характеристики дискретного канала без памяти
2.4.1. Множества. Вероятность
Рассмотрение дискретного канала без памяти следует начинать с напоми- нания некоторых определений теории множеств и теории вероятностей.
Предположим, что элементарное (одиночное) событие ???? происходит на множестве ???? = {????} = {????
1
, ????
2
, … , ????
????
} всех возможных элементарных событий
(выборочном пространстве). Каждое элементарное событие принадлежит од- ному и только одному ????
????
из множества
???? = {????
1
, ????
2
, … , ????
????
}. Событие ???? ∈ ???? явля- ется подмножеством выборочного пространства. Заметим, что если ???? – множе- ство, содержащее ???? элементов, то количество различных подмножеств равно
2
????
. Например, для {
????} = {0, 1} подмножествами являются {0}, {1}, {0, 1 }, {∅}.
Множество чисел ???? = {????(????
1
), ????(????
2
), … , ????(????
????
)} задает распределение веро- ятностей ????(????) на множестве {????}, если выполняется условие нормировки
∑ ????(????
????
) = 1.
????
????=1
Предположим также, что элементарное событие ???? происходит на выбороч- ном пространстве ???? = {????} = {????
1
, ????
2
, … , ????
????
}. Событие ???? ∈ {????} является также подмножеством выборочного пространства.
Множество ???? = {????(????
1
), ????(????
2
), … , ????(????
????
)} задает распределение вероятно- стей ????(????) на множестве {????} c условием
∑ ????(????
????
) = 1.
????
????=1
Рассмотрим некоторые операции над множествами ???? и ????.
На множествах ???? и ???? определена операция пересечения ????⋂???? (произведе- ние событий).
С точки зрения теории вероятностей, событие ????⋂???? можно характеризовать как одновременное осуществление событий ???? и ????.
Множества ????, ????, ???? … являются попарно непересекающимися (попарно несовместны), если никакие два из них не имеют общих элементов, т. е. если
???? ∩ ???? = ∅, ???? ∩ ???? = ∅, … , ???? ∩ ???? = ∅, …. (2.2)
На множествах ???? и ???? определена операция объединения ???? ∪ ???? (сумма со- бытий).

20
На множествах ???? и ???? определена операция разности (???? − ????) множеств.
Пусть заданы два множества элементов декартова произведения
???? = {(0, 1), (0, 3), (4, 5)} и ???? = {(0, 3), (0, 6)}.
Тогда разность (???? − ????) = {(0, 1), (4, 5)}. Рис. 2.3. иллюстрирует операцию разности двух множеств.
Рис. 2.3. Разность множеств (???? − ????)
Далее покажем, что на пересекающихся множествах ???? и ???? справедлива формула вероятности
????(???? ∪ ????) = ????(????) + ????(????) − ????(????⋂????).
На рис. 2.4. показаны пересекающиеся множества ???? и ????, а также непересе- кающиеся множества (???? − ????), (???? − ????), (????⋂????).
Рис. 2.4. Пересечение, непересечение и разности множеств

21
Рассматривая рис. 2.4, можно записать следующие выражения для пересе- кающихся множеств:
???? ∪ ???? = (???? − ????) ∪ (???? − ????) ∪ (????⋂????),
????(???? ∪ ????) = ????((???? − ????) ∪ (???? − ????) ∪ (????⋂????)).
Так как (???? − ????), (???? − ????), (????⋂????) – непересекающиеся множества,
????(???? ∪ ????) = ????(???? − ????) + ????(???? − ????) + ????(????⋂????). (2.3)
Как видно из рис. 2.4 множество ???? состоит из непересекающихся мно- жеств:
???? = (???? − ????) ∪ (????⋂????).
Тогда справедливо
????(????) = ????((???? − ????) ∪ (????⋂????)) = ????(???? − ????) + ????(????⋂????).
По аналогии получаем выражения:
???? = (???? − ????) ∪ (????⋂????),
????(????) = ????((???? − ????) ∪ (????⋂????)) = ????(???? − ????) + ????(????⋂????).
Сумма вероятностей ????(????) + ????(????) равна
????(????) + ????(????) = ????(???? − ????) + ????(????⋂????) + ????(???? − ????) + ????(????⋂????).
Далее сгруппируем слагаемые следующим образом:
????(????) + ????(????) = [????(???? − ????) + ????(???? − ????) + ????(????⋂????)] + ????(????⋂????). (2.4)
Подставляя (2.3) в (2.4), получаем:
????(????) + ????(????) = ????(???? ∪ ????) + ????(????⋂????).
Таким образом, на пересекающихся множествах ???? и ???? справедлива фор- мула вероятности
????(???? ∪ ????) = ????(????) + ????(????) − ????(????⋂????). (2.5)
Если события несовместны, т. е. ????⋂???? = ∅, то формула (2.5) записывается в виде

22
????(???? ∪ ????) = ????(????) + ????(????). (2.6)

1   2   3   4   5   6   7   8   9   ...   17