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

 

Безусловные вероятности  появления символов на выходе источника  сообщений равны: p(a₁) = 0,4; p(a₂) = 0,2; p(a₃) = 0,1; p(a₄) = 0,3. Длительность передачи одного символа τ = 0,0002, передано сообщение из 400 символов.

Вычислить информационные характеристики дискретного канала связи, включая I(a_i), H(A), H(B/a_i), H(B/A), p(b_j), H(B), I(A,B), n, H’(A), R, C, K_э, R_кр.

Проверить выполнение теорем Шеннона про скорость передачи и  про кодирование. Сделать вывод  про надежность и эффективность  канала связи.

 

А. Вычислим канальную матрицу объединения:

Зная КМИ можно вычислить КМО по формуле:

p(a_i;b_j) = p(a_i) * p(b_j/a_i)

 

Канальная матрица объединения

 

p(ai;bj) =	0,39	0	0	0
	0,03	0,15	0,02	0
	0,03	0,02	0,05	0,01
	0	0,01	0,01	0,29

 

Проверка:

ΣΣ p(a_i;b_j) = 0,39 + 0 + 0 + 0 + 0,03 + 0,15 + 0,02 + 0 + 0,03 + 0,02 + 0,05 +

+ 0,01 + 0 + 0,01 + 0,01 + 0,29 = 1

 

Вывод: КМО составлена правильно.

 

Б. Зная КМО, найдем КМП:

 

p(a_i/b_j) = p(a_i;b_j) / p(b_j)

 

p(b₁) = 0,39 + 0,03 + 0,03 + 0 = 0,45

p(b₂) = 0 + 0,15 + 0,02 + 0,01 = 0,18

p(b₃) = 0 +0,02 +0,05 +0,01= 0,08

p(b₄) = 0 + 0 + 0,01 + 0,29 = 0,29

Канальная матрица приемника

 

p(ai/bj)=	0,88	0,02	0,05	0
	0,07	0,84	0,24	0
	0,05	0,11	0,60	0,02
	0	0,03	0,11	0,98

Проверка:

Σ p(a₁/b_j) = 0,88 + 0,07 + 0,05 +0 =1

Σ p(a₂/b_j) = 0,02 + 0,84 + 0,11 +0,03 = 1

Σ p(a₃/b_j) = 0,05 + 0,24 + 0,60 +0,11 = 1

Σ p(a₄/b_j) = 0 + 0 + 0,02 + 0,98 = 1

Вывод: КМИ составлена правильно.

2.4 Характеристики  источника сообщений

1. Количество  информации I(a_i) каждого символа b₁, b₂, b₃, b₄ дискретного сообщения В:

I(a_i) = – log p(a_i)

I(a₁) = – log p(a₁) = –log 0,4 = 1,321928

I(a₂) = – log p(a₂) = – log 0,2 = 2,321928

I(a₃) = – log p(a₃) = – log 0,1 = 3,321928

I(a₄) = – log p(a₄) = – log 0,3 = 1,736966

2. Среднее  количество информации на символ  сообщения определяет энтропию  источника сообщений H(A):

 

H(A) = 1,8464 бит/символ

Максимальная  энтропия источника сообщений H_max(A):

H_max(A) = log 4 = 2 [бит/символ]

3. Информационные  потери при передаче каждого  символа определяют частную условную  энтропию источника H(B/a_i)

, (i=1,2,3,4), [бит/символ]

H(B/a₁) = – (0,98 log 0,98 + 0,01 log 0,01 + 0,01 log 0,01 + 0) = 0,1614бит/симв

H(B/a₂) = – (0,15 log 0,15 + 0,75 log 0,75 + 0,10 log 0,10 + 0) = 1,054бит/симв

H(B/a₃) = – (0,25 log 0,25 + 0,20 log 0,20 + 0,50 log 0,50 + 0,05 log 0,05 ) =

=1,6805бит/симв

H(B/a₄) = – (0 + 0,02 log 0,02 + 0,03 log 0,03 + 0,95 log 0,95 ) = 0,3349бит/симв

4. Средние  потери информации при передаче  одного символа определяет общую  условную энтропию источника  H(B/A):

 

= 0,4 * 0,1614+ 0,2 * 1,054 + 0,1 * 1,6805 + 0,3 * 0,3349 =

= 0,5439 бит/символ

5. Общие  потери информации в канале  связи при передачи сообщения  из 400 символов ΔI:

ΔI = k H(B/A) = 400 * 0,5439 = 217,5644 бит,

где k – количество символов в переданном сообщении.

2.5 Характеристики приемника сообщения

1. Безусловные вероятности появления сигналов на входе приемника p(b_j) определяются по форме:

, (j = 1,2,3,4)

p(b₁) = 0,4 * 0,98 + 0,2 * 0,15 + 0,1 * 0,25 + 0 = 0,447

p(b₂) = 0,4 * 0,01 + 0,2 * 0,75 + 0,1 * 0,20 + 0,3 * 0,02 = 0,18

p(b₃) = 0,4 * 0,01 + 0,2 * 0,10 + 0,1 * 0,50 + 0,3 * 0,03 = 0,083

p(b₄) = 0 + 0 + 0,1 * 0,05 + 0,3 * 0,95 = 0,29

Проверка:

 

2. Среднее количество информации, принятое приемником на один символ, определяется энтропией приемника H(B):

 

= – ( 0,447 log 0,447 + 0,18 log 0,18 + 0,083 log 0,083 + 0,29 log 0,29) =

= 1,7805 бит/символ

Максимальная  энтропия источника сообщений H_max(B):

H_max(B) = log 4 = 2 [бит/символ]

 

3. Среднее количество полученной приемником информации, полученная приемником на один символ с учетом потерь информации, пораженной помехами, I(A,B):

I(A,B) = H(B) – H(B/A) = 1,7805 – 0,5439 = 1,2366 бит/символ

2.6 Скоростные характеристики

1. Скорость модуляции дискретного источника сообщений, n:

 

2. Продуктивность дискретного источника сообщений, H’(A):

 

3. Скорость передачи информации, R:

 

в данном случае скорость равна

 

4. Пропускная способность (емкость) С дискретного канала связи определяется максимальной скоростью передачи С = max R:

 

в данном случае

 

5. Коэффициент эффективности дискретного канала связи К_э

 

6. Критическая скорость передачи R_кр:

 

2.7 Рекомендации и вывод по надежности и эффективности канала

1. Теорема  Шеннона о скорости передачи

R < R_кр

6182,9567 < 3942,99   не выполняется

2. Теорема  Шеннона о кодировании

H’(A) < C

9232 < 7280,5   не выполняется

3. Рекомендации  по повышению надёжности и  эффективности

Так как теоремы о скорости передачи не выполняется, восстановление исходного сообщения становится невозможным.

Существует способ кодирования  и декодирования информации, при  котором вероятность ошибки может  быть очень большой. Для увеличения значения С, требуется увеличить  количество символов сообщения.

В данной работе теоремы  Шеннона не выполняются, следовательно, канал связи не является надежным и эффективным.

3. Оптимальное кодирование

3.1 Назначение ОНК

Оптимальный неравномерный код (ОНК) – это такой код, для которого средняя длина кода является минимальной.

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

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

Основная идея оптимального кодирования: символам сообщения, которые  имеют большую вероятность, присваиваются  короткие бинарные коды, то есть образуются бинарные кодовые слова разной длины  – неравномерные коды.

Оптимальное кодирование  позволяет:

• сжимать время передачи данных при той же скорости;
• уменьшать возможные потери и искажения информации;
• сжимать данные (компрессия);
• архивировать данные;
• эффективно использовать память.

3.2 Равномерный двоичный код

Сообщение:

Х={ТОПАЛОВА АЛЕКСАНДРА АЛЕКСАНДРОВНА}.

Длина сообщения:

L_x= 32 [символ].

Алфавит сообщения:

А={А, В, Д, Е, К, Л, Н, О, П, Р, С, Т, пробел}.

Длина алфавита:

L_А= 13 [символ].

 

Вероятности символов алфавита и равномерный двоичный код РДК

 

i	ai	V(ai)	Р(ai)	РДК
1	А	8	0,24	0001
2	О	3	0,09	0010
3	Л	3	0,09	0011
4	Н	3	0,09	0100
5	В	2	0,06	0101
6	Д	2	0,06	0110
7	Е	2	0,06	0111
8	К	2	0,06	1000
9	Р	2	0,06	1001
10	С	2	0,06	1010
11	ПРОБЕЛ	2	0,06	1011
12	П	1	0,03	1100
13	Т	1	0,03	1101

 

L_РДК = 4 [бит].

L_Sрдк = L_х * 4 = 33 * 4 =132 [бит].

 

Проверка:

Σ p(a_i) = 0,2424 + 0,0606*7 + 0,0909*3 + 0,0303*2=1;

Σ V_i =33 [символ];

все правильно.

 

S_РДК = 110100101100000100110010010100011011000100110111100010100001010001101

  001000110110001001101111000101000010100011010010010010101000001

3.2.1 Корневое бинарное дерево РДК

(4–ого порядка)

 

3.3 Метод Шеннона–Фано

3.3.1 Алгоритм метода бисекции вычисления ОНК:

• предварительный шаг: вероятности ранжируются по убыванию или возрастанию;
• шаг 1: все вероятности делятся на две равновероятные группы; символам верхней строки секции назначается 0, нижним – 1 (или наоборот); т.о. вычислен первый бит ОНК;
• шаг 2: каждую группу делим на две равновероятные подгруппы; верхним – 0, нижним –1 (или наоборот). Вычислен второй бит и т. д.

Деление заканчивается, когда  в подгруппе остается 1 символ.

 

Для однозначности кодирования  и декодирования оптимальных  неравномерных кодов необходимо, чтобы они были префиксными, т.е. для них должен выполняться критерий Фано: ни одно кодовое слово ОНК  не является началом другого кодового слова ОНК.

 

i	ai	Vi	Р(ai)	1й бит	2й бит	3й бит	4й бит	5й бит	ОНК	ИОНК	Li	Li*P(ai)	H(ai)
1	А	8	0,24	0,52  →0	→0				00	11	2	0,48	0,49
2	О	3	0,09		0,39  →1	0,18  →0	→0		0100	1011	4	0,36	0,31
3	Л	3	0,09				→1		0101	1010	4	0,36	0,31
4	Н	3	0,09			0,15  →1	→0		0110	1001	4	0,36	0,31
5	В	2	0,06				→1		0111	1000	4	0,24	0,24
6	Д	2	0,06	0,48  →1	0,24  →0	0,12  →0	→0		1000	0111	4	0,24	0,24
7	Е	2	0,06				→1		1001	0110	4	0,24	0,24
8	К	2	0,06			0,12  →1	→0		1010	0101	4	0,24	0,24
9	Р	2	0,06				→1		1011	0100	4	0,24	0,24
10	С	2	0,06		0,18  →1	→0			110	001	3	0,18	0,24
11	ПРОБЕЛ	2	0,06			0,12  →1	→0		1110	0001	4	0,24	0,24
12	П	1	0,03				0,06  →1	→0	11110	00001	5	0,15	0,15
13	Т	1	0,03					→1	11111	00000	5	0,15	0,15
	Сумма											3,48	3,44