Xreferat.com » Рефераты по информатике и программированию » Расчет информационных характеристик дискретного канала

Расчет информационных характеристик дискретного канала

Размещено на /

Содержание


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

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

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

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

2. Канальная матрица (КМИ; КМП; КМО) и их взаимосвязь

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

3. Информационные характеристики источника сообщений

3.1 Количество информации Расчет информационных характеристик дискретного канала источника

3.2 Информационные потери Расчет информационных характеристик дискретного канала

4. Информационные характеристики приемника

4.1 Количество информации Расчет информационных характеристик дискретного канала приемника

4.2 Информационные потери Расчет информационных характеристик дискретного канала

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

5.1 Скорость модуляции Расчет информационных характеристик дискретного канала симв/сек;

5.2 Производительность источника Расчет информационных характеристик дискретного канала бод;

5.3 Скорость передачи Расчет информационных характеристик дискретного канала или Расчет информационных характеристик дискретного канала бод;

5.4 Емкость канала Расчет информационных характеристик дискретного канала или Расчет информационных характеристик дискретного канала бод;

5.5 Коэффициент эффективности дискретного канала Расчет информационных характеристик дискретного канала;

5.6 Теоремы Шеннона о критической скорости и кодированию

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

6. Оптимальное кодирование. Идея сжатия

6.1 Равномерный двоичный код (РДК), корневое бинарное дерево РДК, длина кода РДК, сообщение в РДК

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

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

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

7. Помехоустойчивое кодирование. Назначение

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

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

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

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

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

7.2 Корректирующий систематический код Хэмминга: генерация, диагностика, коррекция, декодирование

7.3 Корректирующий циклический код: генерация, диагностика, коррекция, декодирование

7.4 Корректирующий мажоритарный код: генерация, диагностика, коррекция, декодирование (другие названия – код по голосованию, К-удвоения)

7.5 Эффективность помехоустойчивых кодов

8. Криптографическое кодирование. Назначение

8.1 Основы криптографического кодирования

8.2 Принципы криптографии по Шеннону

8.3 Требования к криптографическим алгоритмам

8.4 Криптографическое правило Кирхгофа

8.5 Абсолютно стойкий ключ по Шеннону

8.6 Жизненный цикл конфиденциальности данных

8.7 Критерии взлома ключа

8.8 Классификация криптографических методов


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


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


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


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


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


Расчет информационных характеристик дискретного канала

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


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

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

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


Расчет информационных характеристик дискретного канала

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


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

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

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

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

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

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

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

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

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

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

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

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

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


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


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

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

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

Криптокод;

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

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

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

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

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

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


P(ai) = vi/ls


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

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

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

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


I(ai) ≥ 0


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


Расчет информационных характеристик дискретного канала

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


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


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


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


I(a1, a2, a3) = I(a1) + I(a2) + I(a3)


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

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

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

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

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


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


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

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

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


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


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

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


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


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

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


Н(A) ≥ 0


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


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


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


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


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

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


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


Расчет информационных характеристик дискретного канала

Рис.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 la = log16 = 4 [бит/символ]

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


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


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

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

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

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

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

Каждая строка КМИ представляет собой распределение условных вероятностей принятых сигналов Расчет информационных характеристик дискретного канала относительно переданных сигналов Расчет информационных характеристик дискретного канала. Все эти условные вероятности p(bj/ai) и образуют КМИ.


Расчет информационных характеристик дискретного канала


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

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

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


Расчет информационных характеристик дискретного канала

Расчет информационных характеристик дискретного канала


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

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

КМО состоит из совместных вероятностей появления сигналов Расчет информационных характеристик дискретного канала и Расчет информационных характеристик дискретного канала - р(ai ,bj) и отражает действие помех на канале связи.

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


Расчет информационных характеристик дискретного канала


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

Из КМО в КМИ


p(bi/aj) = Расчет информационных характеристик дискретного канала Расчет информационных характеристик дискретного канала

p(ai) = Расчет информационных характеристик дискретного каналаp(ai,bj) (i=1,2…n)


Из КМИ в КМО


Расчет информационных характеристик дискретного канала Расчет информационных характеристик дискретного канала


Из КМО в КМП


p(ai/bj) = Расчет информационных характеристик дискретного канала Расчет информационных характеристик дискретного канала

p(bj) = Расчет информационных характеристик дискретного каналаp(ai,bj) (j=1,2…n)


Из КМП в КМО


p(ai, bj) = p(bj) ·p(ai/bj) Расчет информационных характеристик дискретного канала


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


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

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

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


Расчет информационных характеристик дискретного канала (i=1,2…n)


Условные вероятности главной диагонали КМИ отражают вероятность правильного приема сигналов Расчет информационных характеристик дискретного канала относительно переданных сигналов Расчет информационных характеристик дискретного канала;

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

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


Расчет информационных характеристик дискретного канала


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

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

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


Расчет информационных характеристик дискретного канала (j=1,2…n)


Условные вероятности главной диагонали КМП отражают вероятность правильного приема сигналов Расчет информационных характеристик дискретного канала относительно переданных сигналов Расчет информационных характеристик дискретного канала;

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

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


Расчет информационных характеристик дискретного канала


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


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

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

Расчет информационных характеристик дискретного канала (i=1,2…n)

Σ p(ai) = 1


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


Расчет информационных характеристик дискретного канала (j=1,2…n)


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


Расчет информационных характеристик дискретного канала

Σ p(bj) = 1


3. Информационные характеристики источника сообщений


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

Алфавитом сообщения называются символы, которые входят в сообщение. Например:


A={a1, a2,…,an}


Кортеж упорядоченных уникальных символов – это упорядоченная последовательность символов.


Х={х1, х2,…, хn} – сообщение – кортеж символов


Дискретный ансамбль сообщения (ДАС) – сообщение с вероятностями символов ДАС {Х, p(хi) или A, p(ai)}


3.1 Количество информации Расчет информационных характеристик дискретного канала источника сообщений


Количество информации

Количеством информации символа сообщения определяется:


I(ai) = - log2(p(ai)) = - log(p(ai)) [бит] (i=1,2…n)


В Шенноновской теории информации количество информации источника определяется вероятностью появления символа.


I(ai) = - ln(p(ai)) [нат]

I(ai) = - lg(p(ai)) [дит]


Каждый символ сообщения содержит своё количество информации.

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

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


I(ai) >= 0


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

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


р(ai) = 1 ⇒ I(ai) = 0


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


I(a1, a2, a3) = I(a1) + I(a2) + I(a3)


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


Расчет информационных характеристик дискретного канала [бит/символ]


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

1. Энтропия неотрицательна: Н(А) ≥ 0


2. Энтропия равна нулю тогда и только тогда, когда вероятность символа равна 1: Н(ai) = 0 ⇔ р(ai) =1

3. Энтропия ограничена: H (ai) ≤ log n [бит/символ]

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

4. Максимальная энтропия равна: Hmax(А) = log n [бит/символ]


3.2 Информационные потери Расчет информационных характеристик дискретного канала


Существует два вида условной энтропии, которые определяют действия помех на дискретном канале – это частная условная энтропия (ЧУЭ) и общая условная энтропия (ОУЭ).

Частная условная энтропия источника (ЧУЭИ) сообщений отображает количество потерь информации при передаче каждого сигнала аi :


H(В/аi) = − Расчет информационных характеристик дискретного каналаp(bj/ai)log p(bj/ai) (i = 1,2…n) [бит/символ]


Общая условная энтропия источника (ОУЭИ) определяет средние потери количества информации на принятый сигнал Расчет информационных характеристик дискретного канала относительно переданных сигналов Расчет информационных характеристик дискретного канала.


Расчет информационных характеристик дискретного канала [бит/символ]


4. Информационные характеристики приемника сообщений


4.1 Количество информации Расчет информационных характеристик дискретного канала приёмника


Количество информации

Количеством информации символа сообщения определяется:


I(bj) = - log2(p(bj)) = - log(p(bj)) [бит] (j=1,2…n)


В Шенноновской теории информации количество информации приемника определяется вероятностью появления символа.


I(bj) = - ln(p(bj)) [нат]

I(bj) = - lg(p(bj)) [дит]


Каждый символ сообщения содержит своё количество информации.

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

1. Количество информации неотрицательно: I(bj) ≥ 0

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

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


р(bj) = 1 ⇒ I(bj) = 0


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


I(b1, b2, b3) = I(b1) + I(b2) + I(b3)


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


Расчет информационных характеристик дискретного канала [бит/символ]


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

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


Н(А) ≥ 0


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


Н(ai) = 0 ⇔ р(ai) =1


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


H (B) =< log n [бит/символ]


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

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


Hmax(B) = log n [бит/символ]

Расчет информационных характеристик дискретного каналаРасчет информационных характеристик дискретного каналаРасчет информационных характеристик дискретного канала

4.2 Информационные потери Расчет информационных характеристик дискретного канала


Существует два вида условной энтропии, которые определяют действия помех на дискретном канале – это частная условная энтропия (ЧУЭ) и общая условная энтропия (ОУЭ).

Частная условная энтропия приемника (ЧУЭП) сообщений определяет потери информации каждого принятого сигнала Расчет информационных характеристик дискретного канала.


H(A/ bj) = − Расчет информационных характеристик дискретного каналаp(ai/bj)log p(ai / bj) (j = 1,2…n) [бит/символ]


Общая условная энтропия приемника (ОУЭП) определяет средние потери информации на символ Расчет информационных характеристик дискретного канала при приеме ансамбля {B, p(Расчет информационных характеристик дискретного канала)}:


Расчет информационных характеристик дискретного канала [бит/символ]


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


5.1 Скорость модуляции Расчет информационных характеристик дискретного канала [симв/сек]


Расчет информационных характеристик дискретного канала [симв/сек],


где Расчет информационных характеристик дискретного канала - длительность передачи одного сигнала

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


Расчет информационных характеристик дискретного канала


5.2 Производительность источника Расчет информационных характеристик дискретного канала бод;


Производительность источника - количество бит, вырабатываемых в единицу времени - 1 секунду.


Расчет информационных характеристик дискретного канала [бод]


5.3 Скорость передачи Расчет информационных характеристик дискретного канала или Расчет информационных характеристик дискретного канала бод;


Скорость передачи источника:


Расчет информационных характеристик дискретного канала [бит/сек], [бод]


Скорость передачи приёмника:


Расчет информационных характеристик дискретного канала [бит/сек], [бод]


5.4 Емкость канала Расчет информационных характеристик дискретного канала или Расчет информационных характеристик дискретного канала бод;


Емкость канала (пропускная способность канала) - это максимальное

количество бит, передаваемое в единицу времени – секунду.

Пропускная способность – максимальная скорость передачи.


C=maxR


Емкость канала источника:


Расчет информационных характеристик дискретного канала [бит/сек], [бод]


Емкость канала приёмника:


Расчет информационных характеристик дискретного канала [бит/сек], [бод]


5.5 Коэффициент эффективности дискретного канала Расчет информационных характеристик дискретного канала


Чем больше коэффициент эффективности дискретного канала стремится к единице, тем эффективнее канал и тем меньше информационные потери на нём.


Расчет информационных характеристик дискретного канала

Расчет информационных характеристик дискретного канала


5.6 Теоремы Шеннона о критической скорости и кодировании


Теорема о критической скорости:

Теорема определяет критическую скорость передачи Расчет информационных характеристик дискретного канала, зависящую только от распределения вероятности, при которой существует способ передачи со скоростью R (Расчет информационных характеристик дискретного канала), при котором возможно восстановление исходного сообщения (Расчет информационных характеристик дискретного канала), где С – пропускная способность канала, Н(А) – энтропия источника;

Теорема о кодировании:

Если H’(A) – производительность источника - меньше емкости канала (Расчет информационных характеристик дискретного канала), то существует способ кодирования и декодирования, при котором вероятность ошибки будет сколь угодно мала Расчет информационных характеристик дискретного канала и наоборот.

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

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

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


Расчет информационных характеристик дискретного канала


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

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

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


p(a1)=0.25, p(a2)=0.35, p(a3)=0.15, p(a4)=0.25


2. Расчёты

1) Количество информации I(ai )каждого символа a1, a2, a3 дискретного сообщения :


Расчет информационных характеристик дискретного канала (i=1,2,3) [ бит]

Расчет информационных характеристик дискретного канала [бит]

Расчет информационных характеристик дискретного канала [бит]

Расчет информационных характеристик дискретного канала [бит]

Расчет информационных характеристик дискретного канала [бит]


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


Расчет информационных характеристик дискретного канала

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту

Похожие рефераты: