Конкретные типы дискретных каналов.

Двоичный симметричный канал с шумом.

При наличии шума (помех) в канале передачи входной символ x_j переходит в символ y_i с вероятностью P(y_i/x_j). Обозначим вероятность искажения символа Р

Вероятность его прохождения будет равна P(y_i/x_j) при i = j, что для двоичного канала составит 1 – Р.

Граф симметричного двоичного канала, и матрица вероятностей будут иметь вид.

 

Количество информации, передаваемое одним символом по такому каналу, составит при равновероятных входных символах I_max = 1 – H_min(Y/X), т.к. выше было показано, что в этом случае H_max(Y) = 1.

Находим условную энтропию:

H(Y/X) = -(1-P)log₂(1-P)-Plog₂P

Следовательно:

I = 1 + (1-P)log₂(1-P) + Plog₂P

Если P(x₁) ¹ P(x₂),то H_max(Y) вычисляетсяпо общей формуле

Несимметричный двоичный канал с шумом

Здесь вероятность искажения символа x₁ равна Р₁, а вероятность искажения символа x₂ равна Р₂.

Граф несимметричного двоичного канала, и матрица вероятностей будут иметь вид.

 

 

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

I = H (Y) – H (Y/X)

При этом максимальная энтропия в выходных сигналах рассчитывается по формуле полной энтропии: H(Y) = -Р(у₁)×log₂Р(у₁) - Р(у₂)×log₂Р(у₂)

Энтропия шумов вычисляется по формуле условной энтропии:

H(Y/Х) = -Р(х₁)[Р(у₁/х₁)×log₂Р(у₁/х₁)+Р(у₂/х₁)×log₂Р(у₂/х₁)] -

- Р(х₂)[Р(у₁/х₂)×log₂Р(у₁/х₂) + Р(у₂/х₂)×log₂Р(у₂/х₂)]

 

Двоичный канал передачи со стиранием.

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

Обозначим вероятность стирания символа q, и рассмотрим граф канала со стиранием и соответствующую матрицу вероятностей.

 

 

 

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

где P(y_i) – вероятность возникновения на выходе канала символа y_i.

Для равновероятных символов на входе канала и одинаковой вероятности их искажения Р имеют место следующие соотношения.

Р(х₁) = Р(х₂) = 1/2

Р(у₁) = Р(х₁)Р(у₁/х₁) + Р(х₂)Р(у₁/х₂) = (1-Р-q)/2 + Р/2 = (1-q)/2

Р(у₂) = Р(у₁)

Р(у_С) = Р(х₁)Р(у_С/х₁) + Р(х₂)Р(у_С/х₂) = q/2 + q/2 = q

Отсюда

H(Y) = (1-q)[1-log₂(1-q)]-qlog₂q

Соответственно условная энтропия в общем виде:

Или для рассматриваемого канала:

H(Y/Х) = -(1-Р-q)log₂(1-P-q) + Рlog₂Р + qlog₂q

Отсюда количество информации, передаваемое одним символом по каналу со стиранием при равновероятных входных сигналах и одинаковой вероятности их искажения:

I = (1-q)[1-log₂(1-q)] + (1-Р-q)log₂(1-P-q) + Рlog₂Р

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 8.

Определить полосу пропускания канала передачи на видеомонитор изображения, содержащего 5*10⁵ элементов трех основных цветов. Изображение передается с частотой 25 кадров/с. Каждый элемент имеет 8 равновероятных градаций яркости. Полезный сигнал является шумоподобным, отношение мощностей сигнал/шум равно 15

Решение.

Поток информации, рассчитанный через информационную энтропию, будет равен:

I = -(5*10⁵)*25*3*log₂(1/8) = 112,5×10⁶ (бит/с).

Необходимая полоса пропускания:

F_K = I/D = I/[log₂(1+N_C/N_Ш)] = I/log₂(16) = 112,5*10⁶/4 = 28,125*10⁶ Гц = 28,125 МГц

 

Задача 9.

Определить за какое время можно передать по каналу связи запись музыкального произведения, чтобы при последующем воспроизведении слышимые искажения отсутствовали. Продолжительность произведения 4,5 минуты, полоса частот канала 6 МГц, динамический диапазон канала в 4 раза уже диапазона произведения. Принять, что верхний предел частот, слышимых человеком равен 25 кГц

Решение.

Объем передаваемой информации:

V_C = F_CD_CT_C = 25*10³*D_C*×4,5*60 = 6,75*10⁶*D_C бит.

Поскольку диапазон канала в 4 раза уже диапазона сигнала,
т.е. D_C = 4D_K получим

V_C = 27*10⁶×D_K бит.

Из выражения для объема канала и условия передачи получим:

T_К = V_C /(F_КD_К) = 27*10⁶×D_K/(6*10^6*D_K) = 4,5 с

 

Задача 10.

 

Сигнал подается на вход канала с вероятностью 0,6. Определить количество информации, передаваемое по каналу, если граф канала приведен на рисунке.

Решение.

Матрица вероятностей будет иметь вид: .

Вероятности P(х_i) таковы: P(х₁) = 0,6; P(х₂) = 1 – 0,6 = 0,4.

Рассчитаем вероятности P(y_i).

Р(у₁) = Р(х₁)Р(у₁/х₁) + Р(х₂)Р(у₁/х₂) = 0,6×0,9 + 0,4×0,3 = 0,66;

Р(у₂) = Р(х₁)Р(у₂/х₁) + Р(х₂)Р(у₂/х₂) = 0,6×0,1 + 0,4×0,7 = 0,34

Максимальная энтропия в выходных сигналах:

H(Y) = -Р(у₁)×log₂Р(у₁) - Р(у₂)×log₂Р(у₂) = -0,6× log₂0,6 - 0,4×log₂0,4 = 0,925

Энтропия шумов (условная энтропия):

H(Y/Х) = -Р(х₁)[Р(у₁/х₁)×log₂Р(у₁/х₁)+Р(у₂/х₁)×log₂Р(у₂/х₁)] -

- Р(х₂)[Р(у₁/х₂)×log₂Р(у₁/х₂) + Р(у₂/х₂)×log₂Р(у₂/х₂)] =

= - 0,6[0,9×log₂0,9 + 0,1×log₂0,1] - 0,4[0,3log₂0,3 + 0,7×log₂0,7] = 0,634

Отсюда количество информации, передаваемое по каналу:

I = H (Y) – H (Y/X) = 0,925 – 0,634 = 0,29 бит/знак.

 

Задача 11.

Определить количество информации, передаваемое по двоичному каналу со стиранием с равновероятными сигналами на входе, если вероятность искажения символа равна нулю, а вероятность стирания 0,1.

Решение.

Граф такого канала будет иметь вид, показанный на рис.

Матрица вероятностей передачи:

Вероятности на входе P(х₁) = P(х₂) = 0,5.

Вероятности на выходе:

Р(у₁) = Р(х₁)Р(у₁/х₁) = 0,5×0,9 = 0,45; Р(у₂) = Р(у₁) = 0,45

Р(у_С) = Р(х₁)Р(у_С/х₁) + Р(х₂)Р(у_С/х₂) = 0,5×0,1 + 0,5×0,1 = 0,1

Отсюда максимальная энтропия в выходных сигналах по (6.11):

H(Y) = -Р(у₁)×log₂Р(у₁) - Р(у₂)×log₂Р(у₂) -Р(у_С)×log₂Р(у_С) =

-0,45×log₂0,45 -0,45×log₂0,45 -0,1×log₂0,1 = 1,369

Энтропия шумов по (6.12):

H(Y/Х) = -Р(х₁)[Р(у₁/х₁)×log₂Р(у₁/х₁) + Р(у_С/х₁)×log₂Р(у_С/х₁)] -

- Р(х₂)[Р(у_С/х₂)×log₂Р(у_С/х₂) + Р(у₂/х₂)×log₂Р(у₂/х₂)] =

= - 0,5[0,9×log₂0,9 + 0,1×log₂0,1] - 0,5[0,1log₂0,1 + 0,9×log₂0,9] = 0,469

Отсюда количество информации, передаваемое по каналу по (6.10):

I = H (Y) – H (Y/X) = 1,369 – 0,469 = 0,9 бит/знак.

 

Тема Конечные автоматы

 

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

Конечный автомат имеет один вход и один выход. Он представляет собой объект, функционирующий в дискретные моменты времени t_j. В каждый момент времени автомат находится в одном из возможных состояний z(t_j) (число возможных состояний предполагается конечным). В каждый момент на вход автомата поступает входной сигнал.

Автомат следующим образом реагирует на поступление входных сигналов.

Во-первых, состояние автомата изменяется в соответствии с одношаговой функцией переходов:

z(t_j) = j[ z(t_j-1), x(t_j)]

Во-вторых, в каждый момент автоматного времени на выходеавтомата появляется выходной сигнал y(t_j), определяемый функцией выходов

y(t_j) = y[ z(t_j-1), x(t_j)]

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

Рассмотрим табличный способ задания автомата. При этом используются таблицы переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы - его состояниям. На пересечении i -ой строки и j -го столбца таблицы переходов помещается соответствующее значение j(z_k,x_i) функции переходов, а в таблице выходов - y(z_k, x_i) функции выходов.

При графическом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершин дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал x_k вызывает переход из состояния z_i в состояние z_j, то на графе автомата дуга, соединяющая вершину z_i с вершиной z_j, обозначается x_k. Для того, чтобы задать функцию выходов, дуги графа необходимо дополнительно отметить соответствующими выходными сигналами.

При решении задач моделирования часто более удобной формой является матричное задание конечного автомата. При этом можно рассматривать две матрицы – матрицу переходов и матрицу выходов. Матрица переходов есть квадратная матрица С=|| c_ij ||, строки которой соответствуют исходным состояниям, а столбцы - состояниям перехода. Элемент c_ij соответствует входному сигналу x_k, вызывающему переход из состояния z_i в состояние z_j. Если переход из состояния z_i в состояние z_j происходит под действием нескольких сигналов, элемент матрицы c_ij представляет собой множество входов для этого перехода, соединённых знаком дизъюнкции. Матрица выходов D=|| d_ij || строится аналогично, но ee элемент d_ij соответствует выходному сигналу y_S, выдаваемому при переходе. Для рассматриваемого автомата Мили матрицы имеют вид:

На практике наибольшее распространение получили два класса автоматов - автоматы Мили(Mealy) и автоматы Мура(Moore).

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

Для автомата Мура функция переходов имеет тот же вид, как и у автомата Мили, но функция выходов не зависит от входного сигнала, а является функцией только текущего состояния:

 

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 12.

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

Таблица переходов Таблица выходов.

x z z0 z1 z2 x1 y1 y1 y2 x2 y1 y2 y1

Решение

Граф автомата, заданного исходными таблицами:

Матрицы переходов и выходов:

Поскольку, как состояние автомата, так и его выходной сигнал зависят от входного сигнала и предыдущего состояния, рассматриваемый автомат относится к классу автоматов Мили.

 

Тема Дискретные цепи Маркова

 

Случайный процесс, протекающий в системе A, называется марковским или случайным процессом без последствия, если для любого момента времени t₀ вероятность любого состояния системы при t > t₀ зависит только от ее состояния при t = t₀ и не зависит от того, как и когда система пришла в это состояние. Если число состояний A_i, которые система может принимать, конечно, то такие системы описывает марковский случайный процесс с дискретными состояниями, или марковская цепь.

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

Обычно марковскую цепь изображают в виде графа, вершины которого соответствуют возможным состояниям системы A_i, а дуги - возможным переходам системы из состояния A_i ® A_j. Каждой дуге соответствует переходная вероятность p_ij(k)=p[A_j^(k)/A_i^(k-1)] - это условная вероятность перехода системы на k -ом шаге в состояние A_j при условии, что на предыдущем (k-1)- ом шаге система находилась в состоянии A_i.

Полным описанием марковской цепи служат матрицы переходных вероятностей:

Кроме того, на каждом шаге Марковская цепь характеризуется вектором вероятностей состояний:

|S(t)| = [S₁(t),S₂(t),... S_n(t)]

Вероятностью i- го состояния называется вероятность S_i(t) того, что в момент t система будет находиться в состоянии A_i. Очевидно, что для любого момента t сумма вероятностей всех состояний равна единице:

Марковская цепь называется однородной, если переходные вероятности не зависят от номера шага. Если переходные вероятности меняются от шага к шагу, марковская цепь называется неоднородной.

Все многообразие Марковских цепей подразделяется на эргодические и разложимые.

Эргодические Марковские цепи описываются сильно связанным графом. Это означает, что в такой системе возможен переход из любого состояния A_i в любое состояние A_j (i = 1..n) за конечное число шагов.

Эргодическая цепь Маркова обладает очень важным свойством. При неограниченном увеличении числа шагов (t стремится к бесконечности) вероятности состояний системы [S(t)] стремятся к предельным значениям и перестают изменяться, т.е. зависеть от времени. Система приходит к стационарному режиму, при котором [S] = const.

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

Предельная вероятность состояния имеет четкий смысл: она показывает среднее относительное время пребывания системы в этом состоянии. Например, если предельная вероятность состояния равна 0,5, то это означает, что в среднем половину времени система находится в этом состоянии.

Для определения предельных вероятностей состояний следует решить систему линейных уравнений:

j = 1, …n

Можно показать, что система (5.8) является линейно зависимой, поэтому для ее решения необходимо заменить любое из уравнений условием нормировки вероятностей

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

 

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Задача 13.

Центральный процессор мультипрограммной компьютерной системы в любой момент времени выполняет либо приоритетную программу, либо фоновую программу, либо находится в состоянии ожидания. Продолжительность нахождения системы в каждом состоянии кратна длительности шага - Dt. Определить коэффициент использования процессора, если матрица переходных вероятностей имеет вид:

Решение

Обозначим:

1 - состояние, в котором обслуживается приоритетная программа; 2 - состояние, в котором обслуживается фоновая программа; 3 - состояние простоя.

Изобразим граф функционирования системы.

 

Составим для установившегося режима систему линейных алгебраических уравнений:

S₁ = 0,7S₁ + 0,8S₂ + 0,8S₃

S₂ = 0,2S₁ + 0,1S₂ + 0,05S₃

S₃ = 0,1S₁ + 0,1S₂ +0,15S₃

Заменим любое из них на условие нормировки вероятностей S₁+S₂+S₃=1, а затем решим систему.

В результате решения получаем значение вероятностей состояний в установившемся режиме:

S₁ = 0,73 S₂ = 0,17 S₃ = 0,1

Вероятность простоя процессора S₃ = 0,1.

Коэффициент использования процессора Ки = 1 - S₃ = 0,9

 

Тема Системы массового обслуживания