Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Часть 1. Теория информации

Канальные матрицы (КМИ, КМП, КМО) и их взаимосвязь

 

Канальная матрица определяет действие помех на дискретном канале.

Канальные матрицы бывают трёх видов: канальная матрица источника, канальная матрица приёмника и канальная матрица объединения.

Канальная матрица источника (КМИ)

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

Эта матрица отражает статистические характеристики действия помех. Канальная матрица источника является матрицей прямых переходов переданных сигналов  в принятые сигналы .

Каждая строка КМИ представляет собой распределение условных вероятностей принятых сигналов  относительно переданных сигналов . Все эти условные вероятности p(b_j/a_i) и образуют КМИ.

 

 

Канальная матрица приемника (КМП)

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

Условные вероятности р(a_i /b_j) приёма сигналов  относительно переданных сигналов  составляют канальную матрицу приемника (КМП) и отражают действие помех на канале.

 

 

 

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

Дискретный канал полностью задан канальной матрицей объединения (КМО).

КМО состоит из совместных вероятностей появления сигналов  и  - р(a_i ,b_j) и отражает действие помех на канале связи.

Элементами матрицы являются совместные вероятности:

 

 

Взаимосвязь канальных матриц

Из КМО в КМИ

 

p(b_i/a_j) =

p(a_i) = p(a_i,b_j) (i=1,2…n)

 

Из КМИ в КМО

 

 

 

Из КМО в КМП

 

p(a_i/b_j) =

p(b_j) = p(a_i,b_j) (j=1,2…n)

 

Из КМП в КМО

 

p(a_i, b_j) = p(b_j) ·p(a_i/b_j)

 

Свойства канальных матриц

 

Свойства канальной матрицы источника (КМИ):

1. КМИ – квадратная матрица, то есть её размер nxn ;

2. Сумма условных вероятностей каждой строки равна 1, то есть образует полную группу:

 

 (i=1,2…n)

 

3. Условные вероятности главной диагонали КМИ отражают вероятность правильного приема сигналов  относительно переданных сигналов ;

4. Остальные условные вероятности канальной матрицы (кроме главной диагонали) отражают вероятность ложного приема переданных сигналов;

5. Для идеального канала, на котором нет помех, канальная матрица имеет вид:

 

 

Свойства канальной матрицы приемника (КМП):

1. КМП – это квадратная матрица, то есть её размер nxn ;

2. Сумма условных вероятностей каждого столбца равна 1, то есть образует полную группу:

 

 (j=1,2…n)

 

3. Условные вероятности главной диагонали КМП отражают вероятность правильного приема сигналов  относительно переданных сигналов ;

4. Остальные условные вероятности канальной матрицы приемника (кроме главной диагонали) отражают вероятность ложного приема переданных сигналов;

5. Для идеального канала, на котором нет помех, КМП имеет вид:

 

 

Свойства канальной матрицы объединения (КМО):

 

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

дискретный матрица приемник кодирование

 (i=1,2…n)

Σ p(a_i) = 1

 

2. Сумма совместных вероятностей каждого столбца равна соответствующей безусловной вероятности приемника:

 

 (j=1,2…n)

 

3. Сумма всех элементов канальной матрицы объединения равна 1.

 

Σ p(b_j) = 1

 

 

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

 

5.1 Скорость модуляции  [симв/сек]

 

 [симв/сек],

 

где  - длительность передачи одного сигнала

Если длительность передачи сигналов различна, то вычисляется среднее время передачи одного сигнала.

 

 

5.2 Производительность источника  бод;

Пример расчёта скоростных характеристик для канальной матрицы источника.

1. Исходные данные

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

 

 

Сумма вероятностей каждой строки равна 1,00.

Время передачи символа τ = 0,0002 сек. Передано 250 символов.

Безусловные вероятности появления символов на выходе:

 

p(a₁)=0.25, p(a₂)=0.35, p(a₃)=0.15, p(a₄)=0.25

 

2. Расчёты

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

 

 (i=1,2,3) [ бит]

 [бит]

 [бит]

 [бит]

 [бит]

 

2)Среднее количество информации, переданное одним символом определяет энтропия источника сообщений Н(А):

 

 [бит/символ]

H(A) = -(0,25*(-2) + 0,35*(- 1,51) + 0,15*(- 2,73) + 0,25*(-2) = -(-0,5 - 0,53 – 0,41 – 0,5) = 1,94 [бит/символ]

 

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

 

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

 

где N-количество символов в алфавите сообщения.

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

 

 

 [бит/символ]

H(B/a₁ )= -(0,9*(-0,15) + 0,05*(-4,32) + 0,03*(-5,05)+0,02*(-5,64) =

-(-0,1368 – 0,2161 – 0,1518 – 0,1129) = 0,6175 [бит/символ]

H(B/a₂ )= -(0,1*(-3,32) + 0,84*(-0,25) + 0,06*(-4,05)+0) =

-(-0,3321 – 0,2112 – 0,2435 – 0) = 0,787 [бит/символ]

H(B/a₃ )= -(0 + 0,01*(-6,64) + 0,98*(-0,03)+0,01*(-6,64)) =

-(-0 – 0,0664 – 0,0286 – 0,0664) = 0,1614 [бит/символ]

H(B/a₄ )= -(0 + 0 + 0,01*(-6,64)+0,99*(-0,0145)) =

-(-0– 0 – 0,0664 – 0,0144) = 0,081 [бит/символ]

 

5)Средние потери информации при передаче одного символа определяет общая условная энтропия источника Н(B/А):

 

H(B|A) = 0,25*0,6175 + 0,35*0,787 + 0,15*0,1614 + 0,25*0,081 = 0,1543 + 0,2755 + 0,0242 + 0,02 = 0,4743 [бит/символ]

 

6)Общие потери информации в канале святи при передаче сообщения, состоящего из 250 символов  I

 

 I = k H (B / A) = 250,737476 = 184 [бит]

 

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

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

 

[бит/символ]

p(b₁) = 0,9*0,25 + 0,35*0,1 + 0 + 0 = 0,225 + 0,035 = 0,26

p(b₂) = 0,05*0,25 + 0,84*0,35 + 0,01*0,15 +0 = 0,0125+0,294+0,0015 =0,35

p(b₃) = 0,03*0,25 + 0,06*0,35 + 0,98*0,15+0,01*0,25 = 0,0075+0,021+ 0,147+0,0025 = 0,178

p(b₄) = 0,02*0,25 + 0 + 0,01*0,15 + 0,99*0,25 = 0,005 + 0+0,0015+ 0,2475=0,254

H(B) = -(0,26*(-1,94) + 0,35*(-1,7) + 0,178*(-2,49) + 0,254*(-1,97)) = -

-(-0,5 – 0,5234 – 0,4432 – 0,5) = 1,974 [бит/символ]

 

8) Максимальная энтропия приемника, H_max(B)

 

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

 

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

 

I (A, B) = H (B) – H (B / A) = - = 1,5 [бит/символ]

 

10) Скорость модуляции дискретного канала, n

 

n= = =500 [бод]

 

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

 

H’(A)=  [бод]

H’(A) = = 970,3227 [бод]

 

12) Скорость передачи информации, R

 

R =

R= (1,974 - 0,4743)/0,002 = 749,8676 [бод]

 

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

 

С=

C= = 762,8716 [бод]

 

14) Коэффициент эффективности дискретного канала связи K_э

 

K_э= = =0,9829

 

15) Критическая скорость передачи R_кр

 

R_кр= = = 393,102 [бод]

 

Оценка надёжности и эффективности дискретного канала связи

1. Оценка теоремы Шеннона по скорости

R<R_кр

749,8676 > 393,102

2. Оценка выполнения теоремы по кодированию

H’(A) < C

970,3227 > 762,8716

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

Из-за невыполнения теоремы о скорости передачи невозможным становится восстановление исходного сообщения. При кодировании и декодировании информации вероятность ошибки может быть сколь угодно велика. Для улучшения эффективности необходимо увеличить емкость канала С.

Теоремы Шеннона не выполняются, а значит, наш канал связи не является эффективным и надежным.

Построение канальной матрицы объединения

Найдем безусловные вероятности появления сигналов на входе приемника по формуле:

 

 

Зная КМИ можно построить КМО: р(а_i,,b_j)= p(a_i)p(b_j/а_i)

 

 

Построение канальной матрицы приемника

Зная КМО мы можем построить КМП, найдя элементы по формуле :

 

p(a_i / b_j)= p(a_i,b_j)/p(b_j)

 

Часть 2. Теория кодирования

Оптимальный неравномерный код ОНК Шеннона-Фано, алгоритм расчета ОНК, средняя длина, энтропия, коэффициент сжатия, коэффициент эффективности, сообщение в ОНК, критерий Фано, корневое бинарное дерево ОНК Шеннона-Фано

 

Расчёт ОНК

Оптимальный неравномерный код (ОНК) мы будем рассчитывать по методу Шеннона-Фано, который ещё называют методом бисекции.

Для вычисления ОНК вся работа разбивается на несколько этапов.

Предварительный шаг: вероятности появления символа в сообщении ранжируются по убыванию.

Шаг первый: все вероятности разбиваются на две равновероятные группы. Символам верхней секции назначим 0, символам нижней секции – 1. Первый бит ОНК вычислен.

Шаг второй: каждую группу делим на две равновероятные подгруппы. Верхним подгруппам присваивается 0, нижним – 1. и т. д.

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

 

Нахождение ОНК

 

Критерий Фано однозначного декодирования ОНК: ни одно слово ОНК не является началом другого слова ОНК. Это ещё называется свойством префиксности.

Критерий Фано позволяет однозначно декодировать сжатое сообщение S_ОНК . Сообщение в ОНК будет выглядеть:

S_ОНК=111101100101010111111011010110010011000110010011000010000011001010010010011010111100010001100000

 

 

Характеристики ОНК

1. Средняя длина ОНК

L_cp.онк= 4.23 [бит]

2. Энтропия ОНК

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

3. Максимальная энтропия

H_max= log 17= 4,08 [бит/символ]

4. Относительная энтропия

 

 

5. Информационная избыточность

 

 

6. Абсолютная недогруженость

 

 

7. Коэффициент сжатия

 

К_с = 1- L_cp.онк/ L_РДК = 0,15 = 15 %

 

8. Коэффициент эффективности К_э

 

К_э=Н/ L_cp.онк = 0,27

 

Эффективность ОНК тем выше, чем больше средняя длина ОНК стремится к энтропии.

 

Эффективность ОНК

 

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

Эффективность ОНК можно определить с помощью коэффициента эффективности, то есть чем ближе К_э стремится к единице, тем эффективнее оптимальный неравномерный код.

ОНК не обладает избыточностью, так как к нему не прикрепляются контрольные биты.

 

 

Обнаруживающие коды

 

Двоичный код становится обнаруживающим за счет добавления дополнительных контрольных бит.

Можно назвать следующие обнаруживающие коды: обнаруживающий код четности (ОКЧ), обнаруживающий код удвоения (ОКУ), обнаруживающий код инверсией (ОКИ), обнаруживающий код стандартный телеграфный код № 3 и другие.

 

7.1.1 Обнаруживающий код четности (ОКЧ)

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

n_и - длина информационной части, количество бит.

n_к - длина контрольной части.

 

n = n_и + n_к - длина слова.

 

Пример.

Генерация.

Пусть исходное слово 0101.

Макет ОКЧ - 0101К,

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

 

К = 0 1 0 1 = 0

 

ОКЧ (n; n_и )

ОКЧ (5; 4) = 01010

Проверим:

 

S = 0 1 0 1 0 = 0 -  ошибки , то есть ошибки не существует

 

Количество ошибок	Передано	Принято	Наличие ошибки
Нет ошибок	01010	01010	S = 0,  ошибки
1 ошибка	01010	11010	S = 1,  ошибка
2 ошибки	01010	11011	S = 0,  ошибки
3 ошибки	01010	10011	S = 1,  ошибка
4 ошибки	01010	10111	S = 0,  ошибки

 

Недостаток: ОКЧ позволяет определять наличие ошибки при нечетном их количестве и не определяет ошибку при их четном количестве.

Эффективность.

1. Минимальное количество контрольных бит.

2. Просто и удобный алгоритм генерации кода и диагностики (обнаружения ошибок).

 

7.1.2 Обнаруживающий код удвоения (ОКУ)

Генерация ОКУ.

Пусть исходное сообщение будет 0101.

Макет ОКУ: 0101 К₁ К₂ К₃ К₄,

где n_и = 0101 и n_к = К₁ К₂ К₃ К₄, то есть n_и = n_к.

Контрольные биты равны соответствующим информационным битам.

ОКУ (8; 4) = 01010101

Диагностика.

При диагностике суммируются по модулю 2 информационная и контрольная части ОКУ.

 

 

Во всех остальных случаях ошибка существует.

Передано 01010101.

Принято 00010101.

 

 

Эффективность ОКУ.

1. Обнаруживает любое число ошибок и приблизительно указывает адрес ошибки;

2. Простота алгоритма генерации и диагностики;

3. Недостаток – избыточность, длина контрольной части 100%.

 

7.1.3 Обнаруживающий код инверсии (ОКИ)

Генерация ОКИ.

Пусть исходное сообщение будет 0101.

Макет ОКИ: 0101 К₁ К₂ К₃ К₄,

где n_и = 0101 и n_к = К₁ К₂ К₃ К₄, то есть n_и = n_к.

Контрольные биты ОКИ равны инверсии соответствующих бит

информационной части исходника.

ОКУ (8; 4) = 01011010

Диагностика.

При диагностике суммируются по модулю 2 информационная и

контрольная части ОКУ.

 

 

Если S = 1 – ошибка не существует. S=0 -  ошибка

Передано 01011010.

Принято 10011011.

 

 

Эффективность ОКИ.

1. Обнаруживает любое число ошибок и приблизительно указывает адрес ошибки.

2. Простота алгоритма генерации и диагностики.

3. Недостатком является избыточность, длина контрольной части 100%.

 

7.1.4 Обнаруживающий код Стандартный телеграфный код (ОК СТК №3) №3

Количество единиц в двоичном коде называется весом кода.

Для всех символов, букв, цифр, спецзнаков разработаны двоичные коды весом, равным 3 ( т. е. содержат 3 единицы).

Диагностика.

Если в принятом двоичном слове количество единиц равно 3, то ошибки нет. Во всех остальных случаях ошибка есть.

Символ с ошибкой не корректируется, а удаляется.

 

Часть 1. Теория информации

Система передачи дискретных сообщений

 

Информационные каналы бывают аналоговые (информация в непрерывном виде) и цифровые (дискретные). Широкое развитие получила цифровая техника и дискретные каналы.

 

1.1 Схема, функции блоков источника и приемника

 

Информационную систему передачи данных по каналу связи можно представить крупноблочно (Рис1).

 

Рис1.Крупноблочное представление информационного канала

 

Источник сообщения (ИС) – вырабатывает сообщения, кодеры источника преобразуют сообщения в кодовые слова, используя методы оптимального, помехоустойчивого и криптографического кодирования. Модулятор преобразует бинарные коды в электрические сигналы.

Линия связи (ЛС) – это физическая среда, в которой распространяются сигналы: кабельные, радио и спутниковые линии.

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

 

 

Рис.2.Схема системы передачи дискретных сообщений

 

Функции блоков источника:

· АЦП – алфавитно-цифровой преобразователь (аналоговая информация преобразуется в дискретную);

· Шифратор – устанавливает криптографическую защиту;

· Кодер ОНК (ОНК - оптимальный неравномерный код) - сжимает данные;

· Кодер ПЗК (ПЗК – помехозащищенный код) – устанавливает защиту от помех;

· Модулятор – преобразует цифровую информацию в электрические сигналы;

· Линии связи – телефонные, кабельные, радио, спутниковые.

Функции блоков приемника:

· Демодулятор – преобразует электрические сигналы в двоичный код;

· Декодер ПЗК – определяет наличие ошибки, вычисляет адрес ошибки, корректирует её, снимает помехоустойчивую защиту;

· Декодер ОНК – неравномерный код преобразуется в равномерный двоичный код;

· Дешифратор – снимает криптозащиту;

· ЦАП – цифро-аналоговый преобразователь (дискретную информацию преобразовывает в непрерывную).

 

1.2 Виды информации

 

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

1) Непрерывная информация;

2) Дискретная информация;

3) Криптокод;

4) Оптимальный неравномерный код (двоичный);

5) Помехоустойчивый код;

6) Электрические сигналы.

Расчёт количества информации символов алфавита

Для начала нам необходимо вычислить v_i – частоту появления каждого символа алфавита. Сумма v_i будет равна длине сообщения l_s.

Теперь рассчитываем P(a_i)– вероятность появления символа нашего алфавита в сообщении.

 

P(a_i) = v_i/l_s

 

Сумма таких вероятностей должна быть равна единице.

После этого мы можем найти требуемое количество информации по формуле: I(a_i) = - log(P(a_i)) [бит]

Свойства количества информации:

1. Количество информации не отрицательно:

 

I(a_i) ≥ 0

 

 

2. Чем выше вероятность, тем меньшее количество информации содержит символ.

 

Рис.3. График к свойству 2

 

3. Если вероятность символа равна 1, то количество информации этого символа равно 0:

 

Р(a_i) = 1 ⇒ I(a_i) = 0

 

4. Аддитивность. Количество информации нескольких символов равно сумме количеств информаций каждого:

 

I(a_1, a_2, a₃) = I(a₁) + I(a₂) + I(a₃)

 

Энтропия дискретного ансамбля сообщения

Энтропия – среднее количество информации на символ сообщения.

Расчёт энтропии алфавита

Для вычисления энтропии алфавита нам понадобится l_а - количество символов алфавита.

Максимальная энтропия алфавита будет равна:

 

H_max(А)= log l_a [бит/символ]

 

Причём нужно отметить, что логарифм мы берём по основанию 2.

Расчёт энтропии сообщения

Для нахождения энтропии сообщения нам требуется вычислить такое значение:

 

H (A) = -∑(P(a_i)*logP(a_i)) [бит/символ]

 

Расчёт максимальной энтропии

Максимальную энтропию считаем по формуле:

 

H_max(А)= log l_s [бит/символ]

 

Свойства энтропии:

1. Энтропия не отрицательна:

 

Н(A) ≥ 0

 

2. Энтропия равна нулю тогда и только тогда, когда вероятность символа равна 1.

 

Н(A) = 0 ⇔ Р(a_i) =1

 

3. Энтропия ограничена:

 

H (A) ≤ log l_s [бит/символ]

 

где l_s – количество символов в сообщении.

4. Максимальная энтропия равна:

 

H_max(А ) = log l_s [бит/символ]

 

Рис.4. График к свойству 4

 

Расчётная таблица результатов

В данную таблицу мы внесем все наши результаты расчётов и, как результат, построим график количества информации и график энтропии.

S= (У жизни есть чувство юмора)

А= (У,ж,и,з,н,е,с,т,ь,ч,в,о,ю,м,р,а, .)

 

i	ai	vi	P(ai)	I(ai)	H
1	У	2	0,077	3,700	0,285
2	ж	1	0,038	4,700	0,181
3	и	2	0,077	3,700	0,285
4	з	1	0,038	4,700	0,181
5	н	1	0,038	4,700	0,181
6	е	1	0,038	4,700	0,181
7	с	2	0,077	3,700	0,285
8	т	2	0,077	3,700	0,285
9	ь	1	0,038	4,700	0,181
10	ч	1	0,038	4,700	0,181
11	в	2	0,077	3,700	0,285
12	о	2	0,077	3,700	0,285
13	ю	1	0,038	4,700	0,181
14	м	1	0,038	4,700	0,181
15	р	1	0,038	4,700	0,181
16	а	1	0,038	4,700	0,181
17	_	4	0,154	2,700	0,415
Суммы		26	1,000		3,931

 

H(А)= log l_a = log16 = 4 [бит/символ]

H_max(A)= log22= 4,4594 [бит/символ]