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

Министерство  образования и науки Украины

Одесский Национальный Морской Университет

Кафедра «Информационные  технологии»

 

 

 

 

 

 

 

 

 

 

 

Курсовая работа

 

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

 

 

 

 

 

Выполнила:

студентка КСФ II к. 4 гр.

Топалова Александра

Александровна

Поверили:

Ширшков А.К.

Сафонова Н.В.

 

Одесса 2012 

Содержание

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

1.1 Блок-схема  передачи СПДС. 3

1.2 Функции  блоков источника сообщений: 4

1.3 Виды информации: 4

1.4 Виды и  функции линий связи 4

1.5 Функции  блока приемника сообщений: 5

2. Информационные  характеристики дискретного канала 5

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

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

2.3 Расчет  канальных матриц 6

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

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

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

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

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

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

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

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

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

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

3.3.2 КБР ОНК  Шеннона–Фано 14

3.3.3 Информационные  характеристики ОНК Шеннона–Фано 14

3.4 Метод Хаффмена 15

3.4.1 Алгоритм  Хафффмена: 15

3.4.2 КБД ОНК  Хаффмена 16

3.4.3 Информационные  характеристики ОНК Шеннона–Фано 17

4. Помехоустойчивое кодирование 18

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

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

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

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

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

4.2 Корректирующие  коды 21

4.2.1 Корректирующий  систематический код Хэмминга (КСК  Хэмминга) 21

4.3 Корректирующий  циклический код (КЦК) 23

4.4 Коды, корректирующие  кратную ошибку 26

4.4.1 Корректирующий мажоритарный код (КМК)(код по голосованию)  (К – удвоения) 26

Литература 27

 

 

Информация – с лат. языка «разъяснение, просвещение»:

1. осведомление, сообщение, сведение о чем-либо;
2. обмен сведениями между людьми, между человеком и автоматом (ЭВМ), между автоматами, обмен между животными и растительным миром, передача признаков от клетки к клеткам (наследственность, коды ДНК).

В кибернетике и математике, информация – это количественная мера устранения неопределенности (энтропия).

Теория информации (теория сообщений) – область кибернетики, в которой математическими методами исследуется:

1. способы измерения количества информации;
2. сбора информации;
3. кодирование;
4. преобразование;
5. передача.

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

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

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

Теория кодирования: включает в себя три направления:

1. оптимальное кодирование: сжатие данных без потерь содержания информации;
2. помехоустойчивое кодирование: защита данных от действия помех;
3. криптографическое кодирование: защита данных от несанкционированного доступа (ПСД).

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

1.1 Блок-схема передачи  СПДС.

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

 

источник сообщений

приемник сообщений

1.2 Функции блоков источника сообщений:

1. Аналогово-цифровой преобразователь – преобразует непрерывное сообщение в дискретное.
2. Шифратор – защита от не санкционированного доступа (НСД).
3. Кодер ОНК (оптимальное неравномерное кодирование) – сжимает данные (конверсия).
4. Кодер ПЗК (помехо-защищенного кода) – защита данных от помех.
5. Модулятор – преобразует цифровые данные в электрический сигнал.

1.3 Виды информации:

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

1. непрерывная, аналоговая информация;
2. цифровая, дискретная информация;
3. криптографические коды;
4. оптимальный, неравномерный код, сжатые данные;
5. помехоустойчивый код;
6. электрические сигналы.

Обозначения:

1. Алфавит сообщения – кортеж уникальных символов  А={a₁, a₂, …, a_n};
2. Сообщение – кортеж символов S={s₁, s₂, …, s_n};
3. Вероятность появления символа P(a_i) – для алфавита

                                                         P(x_i) – для символов

Единицы измерения количества информации определяется видом log.

Log – Бит

Ln – Нат

Lg – Дит

1.4 Виды и функции  линий связи

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

Виды линий связи:

1. проводная;
2. кабельная;
3. спутниковая;
4. радио.

Функции: линии связи предназначены для передачи данных на различные расстояния. Информация может менять свою форму при передаче, но содержание при этом сохраняется.

1.5 Функции блока приемника сообщений:

1. Демодулятор – преобразует электрические сигналы в двоичный код.
2. Декодер ПЗК – обнаруживает ошибку, вычисляет ее адрес, корректирует ошибку, снимает контрольные биты.
3. ЦАП (цифрово–аналоговый преобразователь) – преобразует дискретную информацию в аналоговую (непрерывную) – звук, видео и т.д.
4. Дешифратор – снятие защиты от НСД.
5. Декодер ОНК – переход к равномерному двоичному коду.

2. Информационные  характеристики дискретного канала

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

Количество информации символа  сообщения определяется вероятностью появления этого символа в данном сообщении.

I(a_i) =–log₂ p(a_i)

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

1. Количества информации – величина не отрицательная I(a_i) ≥ 0.
2. Чем выше вероятность, тем меньше количества информации. Чем выше вероятность – тем больше информации.

P(a₁) < P(a₂) → I(a₁) > I(a₂)

3. I(a_i) = 0 ↔ P(a_i) = 1(достоверное сообщение).
4. Свойство аддитивности I(a₁) + I(a₂) = I(a₁, a₂).

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

Н (а) = –Σ Р(а_i) log Р(а_i) (бит/символ)

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

1. H (a) ≥ 0
2. H (а) = 0 ≡ а_i Î Х   P (а_i) = 1. Тогда и только тогда в ДАС есть достоверный символ.
3. Энтропия всегда конечна для любого ДАС. H (а) ≤ log n, где n –количество символов сообщения.
4. Для бинарного ДАС, энтропия обладает свойством симметрии.
5. Для сложного ДАС энтропия будет выглядеть так:

H(X, Y) = H(X) + H(Y).

Частотно  условная энтропия источника:

ЧУЭП – определяет информационные потери приемника сообщений B={b₁, b₂,…,b_n} относительно переданного сигнала a_i.

H (B/a_i) = – Σ P(b_j/a_i) log P(b_j/a_i), i=1, 2,…, n

Общая условная энтропия источника:

ОУЭИ – определяет потери информации при приеме ансамбля

B={b₁, b₂,…,b_n} относительно переданного ансамбля А={а₁, а₂...a_n}

H (B/A) = – Σ Σ P(a_i) P(b_j/a_i) log P(b_j/a_i)

Для равно вероятностного а_i Р(а_i) = 1/n (i = 1,2,3...n).

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

H (B/A) = – 1/n Σ Σ P(b_j/a_i) log P(b_j/a_i)

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

Частотно  условная энтропия приемника:

ЧУЭП – определяет информационные потери источника сообщений А={а₁, а₂...a_n} относительно принятого сигнала b_j.

H (A/b_j) = – Σ P(a_i/b_j) log P(a_i/b_j), j=1, 2,…, n

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

ОУЭП – определяет потери информации при передаче ансамбля А={а₁, а₂...a_n} относительно принятого ансамбля B={b₁, b₂,…,b_n}.

H (A/B) = – Σ Σ P(b_j) P(a_i/b_j) log P(a_i/b_j)

Для равно вероятностного b_j Р(b_j) = 1/n (i = 1,2,3...n)

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

H (A/B) = – 1/n Σ Σ P(a_i/b_j) log P(a_i/b_j)

2.3 Расчет канальных  матриц

Теорема 1. «О скорости передачи» Определяет критическую скорость передачи данных R_кр, зависимую только от распределения вероятностей, при которой существует средство передачи со скоростью R близкой к критической (R < R_кр), при которой возможно восстановление начального сообщения (если скорость R < R_кр, восстановление сообщения невозможно). Критическая скорость равняется:

 

где H(A) – энтропия источника, С – пропускная способность канала.

Теорема 2. «О кодировании» Если производительность источника H’(А) меньше пропускной способности канала:

H’(А) < С,

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

 

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

 

p(bj/ai) =	0,98	0,01	0,01	0
	0,15	0,75	0,10	0
	0,25	0,20	0,50	0,05
	0	0,02	0,03	0,95