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

Министерство образования и науки РФ Пензенский государственный университет Кафедра «Информационной безопасности систем и технологий»

Пояснительная записка к курсовой работе по теме:

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

ПГУ 2.10 905.001 ПЗ

Дисциплина: Теория информации

Пенза, 2008 г.

Реферат

АНСАМБЛЬ СООБЩЕНИЯ, ДИСКРЕТНОЕ СООБЩЕНИЕ, ИСТОЧНИК СООБЩЕНИЙ, КАНАЛ БЕЗ ШУМА, КАНАЛ С ШУМОМ, ЭФФЕТИВНОЕ КОДИРОВАНИЕ, ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ, ЭНТРОПИЯ.

Объектом исследования являются источники сообщений, сигналы и кодов.

Целью работы является расчет информационных характеристик источника сообщений, сигналов и кодов.

В процессе работы был произведен расчет различных информационных характеристик источников сообщений, сигналов и кодов.

В результате работы все задачи были решены и все требования задания были выполнены.

Реферат Введение

1. Расчет информационных характеристик источников дискретных сообщений

1.1 Задача № 1.30

1.2 Задача № 1.48

1.3 Задача № 1.67

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

2.1 Задача № 2.24

2.2 Задача № 2.58

3. Согласование дискретного источника с дискретным каналом без шума. Эффективное кодирование

3.1 Задача № 3.24

3.2 Задача № 3.54

3.3 Задача № 3.84

3.4 Задача № 3.114

4. Согласование дискретного источника с дискретным каналом с шумом. Помехоустойчивое кодирование

4.1 Задача № 4.24

4.2 Задача № 4.54

Заключение

Список используемых источников

Эффективная организация обмена информации приобретает все большее значение как условие успешной практической деятельности людей. Объем информации, необходимой для нормального функционирования современного общества, растет примерно пропорционально квадрату развития промышленного потенциала. Доля рабочей силы занятой вопросами обеспечения информацией начинает превышать долю рабочей силы занятой непосредственно в производстве. Поэтому науки, изучающие структуру и закономерности протекания информационных процессов, к числу которых относится и теория информации (ТИ), в такой ситуации становятся исключительно актуальными.

Дисциплина связана с предшествующими ей дисциплинами «Высшая математика», «Теория вероятности и матстатистика», «Дискретная математика» и последующими дисциплинами «Компьютерная электроника», «Вычислительные системы», «Сети ЭВМ», «Надежность, контроль, диагностика и эксплуатация ЭВМ», «Основы защиты информации» и др.

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

В данной курсовой работе проводится расчет основных информационных характеристик источника сообщений, сигналов и каналов. Теория информации представляет собой ветвь статистической теории связи. Информация передается, и хранится в виде сообщений. Сообщение — это информация представленная в какой-либо форме. Первый раздел курсовой работы носит название: «Расчёт информационных характеристик источника дискретного сообщения». Изменяющийся во времени физический процесс, отражающий передаваемое сообщение называется сигналом. Сигнал передаётся по каналу связи. Второй раздел работы называется: «Расчёт информационных характеристик дискретного канала». В оставшихся двух разделах решаются задачи по темам: согласование дискретного источника с дискретным каналом с шумом и без шума, эффективное и помехоустойчивое кодирование. Их решение основываются на постулатах таких ученых как Шеннон, Хаффман, Фано.

1. Расчет информационных характеристик источников дискретных сообщений

1.1 Задача № 1.30

Распределение вероятностей дискретной случайной величины имеет вид:

Определить число n значений случайной величины, при которых энтропия H_p(X) равномерного распределения будет равна энтропии H (X) заданного распределения.

Решение:

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

.

Равномерное распределение предполагает равные вероятности всех возможных исходов, при этом энтропия

.

Из условия, что находим:

Ответ: при объеме алфавита n = 7, энтропия H_p(X) равномерного распределения будет равна энтропии H (X) заданного распределения.

1.2 Задача № 1.48

Найти энтропию шума H (U/Z) в двоичном симметричном канале без памяти, если энтропия источника на входе канала H (U) = 3400(бит), энтропия ансамбля на выходе канала H (Z) = 6800(бит), ненадежность канала H (U/Z) = 700(бит).

Решение:

Энтропия шума в двоичном симметричном канале без памяти будем искать по формуле

.

Выразим, неизвестное нам, количество информации

.

Подставляя эту формулу в исходную, получим выражение для нахождения энтропии шума в двоичном симметричном канале

.

Ответ: энтропия шума в двоичном симметричном канале H (U/Z) = 4100(бит).

1.3 Задача № 1.67

Принимаемый сигнал может иметь амплитуду А₁(событие Х₁) или А₂ (событие Х₂), а также сдвиг фаз (событие Y₁) или (событие Y₂) режимах. Вероятности совместных событий имеют следующие значения: P (X₁, Y₁) = 0,73; P (X₁, Y₂) = 0,21; P (X₂, Y₁) = 0,02; P (X₂, Y₂) = 0,04.

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

Решение:

Количество информации о фазовом сдвиге при известной амплитуде будем искать по формуле (1.13) лекции

.

Найдем энтропию Y:

.

Что бы найти энтропию, найдем вероятности появления событий Y₁ и Y₂:

Найдем вероятности появления событий Х₁ и Х₂:

Подставляя значения в вышестоящую формулу, найдем значение энтропии:

.

По формуле (1.9) лекции найдем Подставляя полученные значения в формулу, получим, что Тогда, количество информации о фазовом сдвиге при известной амплитуде будет равно

.

Ответ: количество информации о фазовом сдвиге при известной амплитуде .

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

2.1 Задача № 2.24

На вход дискретного симметричного канала без памяти поступают двоичные символы U₁ =0 и U₂ = 1 с априорными вероятностями P (U₁) = 0,85 и P (U₂) = 0,15. Переходные вероятности P (Zj / U_i) в таком канале задаются соотношением

где р — вероятность ошибки, р = 0,05. определить все апостериорные вероятности.

Решение:

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

Рис. 2.1

Так как р — вероятность ошибки, следовательно вероятность правильного приема — q, причем

.

Найдем переходные вероятности:

В таком канале каждый кодовый символ может быть принят с ошибочной вероятностью:

.

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

.

По формуле Байеса определим апостериорные вероятности:

;

Ответ: априорные вероятности в данном канале равны: P (U₁/Z₁) = 0,96; P (U₁/Z₂) = 0,23; P (U₂/Z₁) = 0,04; P (U₂/Z₂) = 0,77.

2.2 Задача № 2.58

По каналу связи передаётся сообщение из ансамбля

.

Средняя длительность передачи одного элемента сообщения в канале ф = 0,44 мс. Шум в канале отсутствует. Определить пропускную способность канала и скорость передачи информации.

Решение:

В соответствии с (1.25.а) лекции, в случае, когда шум в канале отсутствует Скорость рассчитаем по формуле

.

Объем алфавита данного сообщения равно восьми, т. е. М = 8. найдем пропускную способность

.

Скорость передачи информации по каналу есть произведения количества информации, передаваемого по каналу на скорость:

.

Количество информации будем искать по формуле (1.13) лекции

.

Так как шум в канале отсутствует, то

.

Тогда, количество информации

.

Определим энтропию заданного распределения. Для нахождении энтропии данного ансамбля воспользуемся формулой (1.4):

.

Подставляя в полученную ранее формулу, получим

.

Ответ: пропускная способность канала С = 18184(бит/с); скорость передачи информации V^, = 5546,12.

3. Согласование дискретного источника с дискретным каналом без шума. Эффективное кодирование

3.1 Задача № 3.24

Закодировать двоичным кодом Фано ансамбль сообщений

Закодировать произвольную комбинацию, состоящую из пяти символов ансамбля А; Определить потенциальный минимум среднего количества символов кода, приходящихся на одно сообщение ансамбля А; Определить среднее количество символов разработанного кода Фано, приходящихся на одно сообщение из ансамбля А; Рассчитать эффективность разработанного кода.

Решение:

Для удобства расположим вероятности появления сообщений в порядке убывания:

Выберем из ансамбля, А произвольную комбинацию из пяти символов и закодируем их полученным кодом Фано:

А₉А₃А₅А₇А₄

110 111 111 101 111 105 233 092 608.

Потенциальный минимум будем искать по формуле (2.12) лекции:

;

Так как код является двоичным, тогда основание кода N = 2. Следовательно:

.

Тогда потенциальный минимум будет равен энтропии источника:

.

Найдем энтропию источника, пользуясь мерой Шеннона:

;

Рассчитаем среднее количество символов, приходящихся на одно сообщение:

где

М — объем алфавита кода (М = 2);

P_i — вероятность появления события;

n — количество символов в коде.

Согласно (2.12.а) лекции эффективность кода находим, как:

.

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

3.2 Задача № 3.54

Закодировать кодом Фано, с объемом алфавита М=5, ансамбль

Закодировать произвольную комбинацию, состоящую из пяти символов ансамбля А; Определить потенциальный минимум среднего количества символов кода, приходящихся на одно сообщение ансамбля А; Определить среднее количество символов разработанного кода Фано, приходящихся на одно сообщение из ансамбля А; Рассчитать эффективность разработанного кода.

Решение:

Для удобства расположим вероятности появления сообщений в порядке убывания:

Выберем из ансамбля, А произвольную комбинацию из пяти символов и закодируем их полученным кодом Фано:

А₁А₂А₃А₄А₅

Потенциальный минимум будем искать по формуле (2.12) лекции:

;

Так как код является четверичным, тогда основание кода N = 5. Следовательно:

.

Найдем энтропию источника, пользуясь мерой Шеннона:

;

Тогда потенциальный минимум

.

Рассчитаем среднее количество символов, приходящихся на одно сообщение:

где

М — объем алфавита кода (М = 5);

P_i — вероятность появления события;

n — количество символов в коде.

Согласно (2.12.а) лекции эффективность кода находим, как:

.

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

3.3 Задача № 3.84

Закодировать двоичным кодом Хаффмана ансамбль сообщений

Закодировать произвольную комбинацию, состоящую из пяти символов ансамбля А; Определить потенциальный минимум среднего количества символов кода, приходящихся на одно сообщение ансамбля А; Определить среднее количество символов разработанного кода Хаффмана, приходящихся на одно сообщение из ансамбля А; Рассчитать эффективность разработанного кода.

Решение:

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

Затем строится кодовое дерево, в процессе которого осуществляется кодирование: верхняя точка дерева равна единице; из нее направляется две ветви, причем, ветви с большей вероятностью приписывается значение «1», а с меньшей — «0». Такое последовательное ветвление продолжается до тех пор, пока не добираются вероятности каждой буквы.

Рис. 3.1

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

Выберем из ансамбля, А произвольную комбинацию из пяти символов и закодируем их полученным кодом Хаффмана:

А₁А₂А₇А₆А₄

11 100 100 010 111 000 404 557 824.

Потенциальный минимум будем искать по формуле (2.12) лекции:

;

Так как код является двоичным, тогда основание кода N = 2. Следовательно:

.

Найдем энтропию источника, пользуясь мерой Шеннона:

;

Рассчитаем среднее количество символов, приходящихся на одно сообщение:

где

М — объем алфавита кода (М = 2);

P_i — вероятность появления события;

n — количество символов в коде.

Согласно (2.12.а) лекции эффективность кода находим, как:

.

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

3.4 Задачи № 3.114

Закодировать кодом Хаффмана, с объемом алфавита М=5, ансамбль

Закодировать произвольную комбинацию, состоящую из пяти символов ансамбля А; Определить потенциальный минимум среднего количества символов кода, приходящихся на одно сообщение ансамбля А; Определить среднее количество символов разработанного кода Хаффмана, приходящихся на одно сообщение из ансамбля А; Рассчитать эффективность разработанного кода.

Решение:

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

Затем строится кодовое дерево, в процессе которого осуществляется кодирование: верхняя точка дерева равна единице; из нее направляется четыре ветви, причем, ветви с большей вероятностью приписывается значение «4», а с меньшей — «0». Такое последовательное ветвление продолжается до тех пор, пока не добираются вероятности каждой буквы.

Рис. 3.2

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

Выберем из ансамбля, А произвольную комбинацию из пяти символов и закодируем их полученным кодом Хаффмана:

А₈А₇А₆А₅А₄

2 023 023 023 322.

Потенциальный минимум будем искать по формуле (2.12) лекции:

;

Так как код является четверичным, тогда основание кода N =5. Следовательно:

.

Найдем энтропию источника, пользуясь мерой Шеннона:

;

Тогда потенциальный минимум

.

Рассчитаем среднее количество символов, приходящихся на одно сообщение:

где

М — объем алфавита кода (М = 5);

P_i — вероятность появления события;

n — количество символов в коде.

Согласно (2.12.а) лекции эффективность кода находим, как:

.

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

4. Согласование дискретного источника с дискретным каналом с шумом. Помехоустойчивое кодирование

4.1 Задача № 4.24

Определить избыточного оптимального по Шеннону кода (существование которого утверждается теоремой для канала с шумом) с объемом алфавита М =3 и средним количеством символов, переданных в единицу времени — V_k, предназначенного для безошибочной передачи информации по каналу с пропускной способностью С. Найти минимально возможную избыточность оптимального кода для симметричного канала с вероятностью ошибки Р = 0,1.

Решение:

В соответствии с (1.12) лекции, избыточность источника дискретного сообщения с объемом алфавита М называется величина

Причем, если ввести понятие производительности

То величину можно переписать в виде:

.

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

.

В соответствии с условием (2.15) теоремы Шеннона или для оптимального кода

где .

Поэтому, окончательная формула для вычисления избыточности будет выглядеть:

.

В соответствии с § 1.6 лекции, среднее количество символов, передающихся в единицу времени будем определять по формуле (1.27.а):

Подставляя полученное значение в выведенную формулу избыточности, получим:

Ответ: минимальная возможная избыточность оптимального кода для симметричного канала с вероятностью ошибки Р = 0,1 и объемом алфавита М = 3 будет равна .

4.2 Задача № 4.54

Построить производящую матрицу G линейного двоичного блочного кода, способного исправлять одиночную ошибку при передаче дискретных сообщений источника, представляющих собой последовательность десятичных цифр из диапазона 0 … M-1 (с объёмом алфавита M = 1981). Пользуясь разработанной матрицей G, сформировать кодовую комбинацию для сообщения i (i = 1569). Построить соответствующую производящей матрице G проверочную матрицу H и с её помощью сформировать кодовую комбинацию для сообщения i. По виду синдрома найти и исправить ошибку в принимаемой кодовой комбинации (дополнительно заданной преподавателем). Определить, является ли разработанный код кодом Хэмминга.

Решение:

Производящая матрица G линейного двоичного блочного кода имеет размерность (n; k). Так как код является двоичным, то

.

Отсюда находим k:

Матрица G линейного двоичного кода состоит из двух матриц:

.

Построим матрицу I: I — это единичная матрица, размерности (k; k), при k = 11

Построим матрицу П: П — имеет размерность (k; n-k), k — число строк, а n — число столбцов.

Матрицу П будем строить по определенным правилам:

1. так как код должен исправлять единичную ошибку, получим, что исправная способность будет равна единице, т. е. .

В одной стоке матрицы должно быть не менее d — 1 единиц. Найдем d как

2. все строки должны быть разными;

3. число элементов в стоке должно быть минимально.

Используя правила построения, получим матрицу П:

n — k = 4

k = 11

n = 15

После построения вспомогательных матриц, можно построить матрицу G:

Проверочная матрица Н имеет размерность (n-k; k) и представляет собой транспонированную матрицу П:

Пользуясь разработанной матрицей G, сформируем кодовую комбинацию для сообщения — i (i =1569). Переведем ее из десятичного в двоичный вид: 1569 11 000 100 001.

Разрешенная комбинация

Получится кодовая комбинация V_i

Полученная комбинация состоит из информационных и проверочных разрядов:

.

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

.

берется из матрицы Н.

j = 1:

j = 2:

j =3:

j = 4:

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

1. по информационным разрядам задается комбинация, определяющая проверочные разряды;

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

Для того, что бы с помощью синдрома найти ошибку, найдем матрицу Н_{проверочную}:

где I — единичная матрица, размерности (n-k; n-k)

Попробуем найти ошибку с помощью синдрома: пусть получена следующая комбинация -. Воспользуемся правилом нахождения синдрома:

1. по информационным разрядам определяем проверочные разряды исходного кода — [1001];

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

[1001][1100] =.

Теперь строим проверочную матрицу Н_{проверочную}:

Найдем в Н_{проверочной} столбец, совпадающий с комбинацией синдрома. Номер этого столбца указывает на номер столбца в принятой комбинации, в которой допущена ошибка. В нашем случае комбинация синдрома совпадает с 2 столбцом Н_{проверочную}.

Для исправления этой ошибки надо инвертировать значение этого разряда. Тогда у нас получается -.

Код Хемминга, это код (n; k), который определяется:

Полученная мной матрица имеет размерность. Она является кодом Хемминга.

Заключение

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

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

В результате выполнения работы все требования задания были выполнены.

Список использованных источников

1. Прикладная теория информации: Учебн. Для студ. ВУЗов по спец. «Автоматизированные системы обработки информации и управления». — М.: Высш. шк., 1989. — 320с.:ил.