Материал: Методические указания к выполнению курсовой работы по дисциплине «Теория информации» для студентов специальности «Компьютерная безопасность». Поздышева О.В., Остапенко А.Г

какого номера) в итоге следующего испытания система перейдет в состояниеj.

Таким образом, в обозначенииpij первый индекс указывает номер предшествующего, а второй − номер последующего состояния. Например, p23 – вероятность перехода из второго состояния в третье.

Пусть число состояний конечно и равноk. Матрицей перехода системы называют матрицу, ко-

торая содержит все переходные вероятности этой системы:

Так как в каждой строке матрицы помещены вероятности событий (перехода из одного и того же состоянияi в любое возможное состояниеj), которые образуют полную группу, то сумма вероятностей этих событий равна единице [1]. Другими словами, сумма переходных вероятностей каждой строки матрицы перехода равна единице:

k

pij 1. i, j 1

Приведем пример матрицы перехода системы, которая может находиться в трех состоянияхA1,A2,A3; переход из состояния в состояние происходит по схеме однородной цепи Маркова; вероятности перехода задаются матрицей:

9

Здесь видим, что если система находилось в состоянииA1, то после изменения состояния за один шаг она с вероятностью 0,5 останется в этом же состоянии, с вероятностью 0,5 останется в этом же состоянии, с вероятностью 0,2 перейдет в состояние A2, то после перехода она может оказаться в состояниях A1,A3; перейти же из состояния A2 в A2 она не может. Последняя строка матрицы показывает нам, что из состояния A3 перейти в любое из возможных состояний с одной и той же вероятностью 0,1.

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

Пример 2. По заданной матрице перехода построить граф состояний.

Т.к. матрица четвертого порядка, то, соответственно, система имеет 4 возможных состояния, приведенных на рис. 9.

10

Источник S определяется как множество разбиений Sj с совокупностью всевозможных условных вероятностей элементов разбиений p(Si 0 j 0 | Si 1 j 1 ...Si n j n ) и p(Si j ).

Источник S называется стационарным , если ве-

Si 1 1 ,Si 1 2 …Si n n обычно отождествляются с соответствующими наборами букв ai1, ai2, … , аin и вместо p(Si n j + n /Si 0

j Si 1 j + 1 ...Si n - 1 j n - j 0 ) пишут p(ain/ai0ai1 … аin-1), подразумевая

под этим вероятность появления буквы аin после набора

букв ai0ai1 … аin-1.

Энтропией стационарного источника S называется величина

H(S)=limH(Sп /S1 S2 ...Sn - 1 ).

Стационарный источник S называется источником Бернулли, если p(Si j /Si 1 j 1 Si 2 j 2 ...Si n j n ) = p(S i j ). Другими словами, S — источник Бернулли, если вероятность появления буквы не зависит ни от места в последовательности, ни от предыдущих букв. Для источника Бернулли новое определение энтропии совпадает с определением, использовавшимся ранее [8, 9]:

12

( ) = ( 1) =

= − ∑ ( 1) log ( 1) =

=1

= − ∑ ( ) log ( ).

=1

Стационарный источник S называется Марковским источником r -го порядка, если

p(Si j /Si n j - n Si n - 1 j - n + 1 ...Si 1 j - 1 )= = p(Si j /Si r j - r Si r - 1 j - r + 1 ... Si 1 j - 1 )

при r≤ п. Другими словами, вероятность появления следующей буквы зависит только от r предыдущих. Если S — Марковский источник r-го порядка, то

H(S) =H(Sr+1/S1 S2... Sr) =

= –∑p(Si 1 1 Si 2 2 ...Si r r Si r + 1 r + 1 )log p(Sir+1r+1/Si11

i1…ir+1

Si22...Sirr)=

= –∑p(ai1… аir+1) log p(аir+1/ai1… аir).

i1…ir+1

Пронумеруем подряд все возможные слова из г

13