Расчет источников сообщений, сигналов и каналов

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

сигнал кодирование информационный дискретный

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

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

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

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

Третий раздел курсового проекта направлен на решение задач в области эффективного кодирования. В первых двух осуществлялось кодирование методом Фано, в остальных - методом Хаффмена.

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

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

Задача №1.26

Распределение вероятностей дискретной случайной величины имеет вид: p(x₁)=0,362133; p(x₂)=0,15; p(x₃)=0,15; p(x₄)=0,1; p(x₅)=0,1; p(x₆)=0,1; p(x₇)=0,01; p(x₈)=0,01; p(x₉)=0,017867. Определить число n значений случайной величины, при которых энтропия H_p(X) равномерного распределения будет равна энтропии H(X) заданного распределения.

Решение:

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

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

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

H_p(X)=log₂n

Ответ: .

Задача №1.41

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

Решение:

Энтропия шума в двоичном симметричном канале без памяти вычисляется по формуле (1.17) лекции:

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

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

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

(бит)

Ответ: энтропия шума в двоичном симметричном канале без памяти составляет бит.

Задача №1.76

Дискретный источник выбирает сообщения из ансамбля . Длительности сообщений соответственно равны: t_u1=0,8c, t_u2=0,6c, t_u3=0,5c, t_u4=0,3c. Определить производительность источника.

Решение:

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

Пользуясь формулой Шеннона, находим:

бит

Среднее время определим как

Откуда

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

(бит/с)

Ответ: производительность источника бит/с.

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

Задача №2.3

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

Определить все апостериорные вероятности .

Решение:

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

Рисунок 2.1

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

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

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



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

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

Используя формулу Байеса, получаем:

Ответ: апостериорные вероятности составляют соответственно , , и .

Задача №2.51

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

Решение:

В соответствие с формулой (1.25а) лекции пропускная способность дискретного канала без шума определяется:

, где М=8,

Подставляя в формулу (1.25а) полученные значения, получаем

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

, где

, т.к. =0,

т.к. шум отсутствует. Энтропию найдем по формуле Шеннона:

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

Ответ: ,

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

Задача №3.3

Закодировать двоичным кодом Фано ансамбль сообщений {a_i}, заданных таблицей 1.

Таблица 1

a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11	a12
0,38	0,12	0,071	0,21	0,013	0,004	0,012	0,03	0,0211	0,1	0,019	0,0199

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

Решение:

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

Таблица 2

a1	0,38	0	0,59	0										00
a4	0,21			1										01
a2	0,12	1	0,41	0	0,22	0								100
a10	0,1					1								101
a3	0,071			1	0,19	0	0,101	0						1100
a8	0,03							1						1101
a9	0,0211					1	0,089	0	0,041	0				11100
a12	0,0199									1				11101
a11	0,019							1	0,048	0				11110
a5	0,013									1	0,029	0		111110
a7	0,012											1	0	1111110
a6	0,004												1	1111111

Выберем из ансамбля сообщений {a_i} произвольную комбинацию из пяти символов и закодируем их полученным кодом Фано:

a₄ a₆ a₈ a₁₀ a₁₂

011111111110110111101

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

Так как код является двоичным, то основание кода . Отсюда следует:

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

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

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

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



Рассчитаем среднее количество символов, приходящихся на одно сообщение, по формуле (2.9) лекции:

m - количество символов в коде.

Количество символов в коде представлено в таблице 3.

Таблица 3

Сообщение	Вероятность события Ps	Количество символов в коде ms
a1	0,38	2
a2	0,12	3
a3	0,071	4
a4	0,21	2
a5	0,013	6
a6	0,004	7
a7	0,012	7
a8	0,03	4
a9	0,0211	5
a10	0,1	3
a11	0,019	5
a12	0,0199	5

Найдем эффективность кода по формуле:

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

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

Задача №3.33

Закодировать троичным кодом Фано ансамбль сообщений, заданных таблицей 4.

Таблица 4

a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11	a12
0,38	0,12	0,071	0,21	0,013	0,004	0,012	0,03	0,0211	0,1	0,019	0,0199

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

Решение:

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

Таблица 5

a1	0,38	0				0
a4	0,21	1	0			10
a2	0,12		1			11
a10	0,1	2	0			20
a3	0,071		1	0		210
a8	0,03			1		211
a9	0,0211		2	0		220
a12	0,0199			1	0	2210
a11	0,019				1	2211
a5	0,013			2	0	2220
a7	0,012				1	2221
a6	0,004				2	2222

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

a₁ a₂ a₃ a₄ a₅

011210102220

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

Так как код является троичным, то основание кода . Отсюда следует:

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

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

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

Рассчитаем среднее количество символов, приходящихся на одно сообщение, по формуле (2.9) лекции:

где P_s - вероятность появления события;

m - количество символов в коде.

Количество символов в коде представлено в таблице 6.

Таблица 6

Сообщение	Вероятность события Ps	Количество символов в коде ms
a1	0,38	1
a2	0,12	2
a3	0,071	3
a4	0,21	2
a5	0,013	4
a6	0,004	4
a7	0,012	4
a8	0,03	3
a9	0,0211	3
a10	0,1	2
a11	0,019	4
a12	0,0199	4

Найдем эффективность кода по формуле:



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

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

Задача №3.63

Закодировать двоичным кодом Хаффмана ансамбль сообщений, представленных в таблице 7.

Таблица 7

a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11	a12
0,38	0,12	0,071	0,21	0,013	0,004	0,012	0,03	0,0211	0,1	0,019	0,0199

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

Решение:

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

Таблица 8

a1	0,38	0,38	0,38	0,38	0,38	0,38	0,38	0,38	0,38	0,381	0,619	1
a4	0,21	0,21	0,21	0,21	0,21	0,21	0,21	0,21	0,239	0,38	0,381
a2	0,12	0,12	0,12	0,12	0,12	0,12	0,12	0,171	0,21	0,239
a10	0,1	0,1	0,1	0,1	0,1	0,1	0,119	0,12	0,171
a3	0,071	0,071	0,071	0,071	0,071	0,071	0,1	0,119
a8	0,03	0,03	0,03	0,0389	0,0501	0,0689	0,071
a9	0,0211	0,0211	0,029	0,03	0,0389	0,0501
a12	0,0199	0,0199	0,0211	0,029	0,03
a11	0,019	0,019	0,0199	0,0211
a5	0,013	0,016	0,019
a7	0,012	0,013
a6	0,004

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

Рисунок 3.1

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

Таблица 9

a1	11
a2	101
a3	000
a4	01
a5	100010
a6	1000110
a7	1000111
a8	10010
a9	10000
a10	001
a11	100110
a12	100111

Выберем из ансамбля сообщений {a_i} произвольную комбинацию из пяти символов и закодируем их полученным кодом Фано:

a₄ a₆ a₈ a₁₀ a₁₂

01100011010010001100111

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

Так как код является двоичным, то основание кода . Отсюда следует:

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



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

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

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

Рассчитаем среднее количество символов, приходящихся на одно сообщение, по формуле (2.9) лекции:

где P_s - вероятность появления события;

m - количество символов в коде.

Количество символов в коде представлено в таблице 10.

Таблица 10

Сообщение	Вероятность события Ps	Количество символов в коде ms
a1	0,38	2
a2	0,12	3
a3	0,071	3
a4	0,21	2
a5	0,013	6
a6	0,004	7
a7	0,012	7
a8	0,03	5
a9	0,0211	5
a10	0,1	3
a11	0,019	6
a12	0,0199	6

Найдем эффективность кода по формуле:

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

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

Задача №3.93

Закодировать троичным кодом Хаффмана ансамбль сообщений, представленных в таблице 11.

Таблица 11

a1	a2	a3	a4	a5	a6	a7	a8	a9	a10	a11	a12
0,38	0,12	0,071	0,21	0,013	0,004	0,012	0,03	0,0211	0,1	0,019	0,0199

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

Решение:

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

Таблица 12

a1	0,38	0,38	0,38	0,38	0,38	0,62	1
a4	0,21	0,21	0,21	0,21	0,29	0,38
a2	0,12	0,12	0,12	0,12	0,21
a10	0,1	0,1	0,1	0,119	0,12
a3	0,071	0,071	0,071	0,1
a8	0,03	0,03	0,06	0,071
a9	0,0211	0,029	0,03
a12	0,0199	0,0211	0,029
a11	0,019	0,0199
a5	0,013	0,019
a7	0,012
a6	0,004

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

Рисунок 3.2

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

Таблица 13

a1	1
a2	20
a3	220
a4	21
a5	22202
a6	22200
a7	22201
a8	2221
a9	22222
a10	221
a11	22220
a12	22221

Выберем из ансамбля сообщений {a_i} произвольную комбинацию из пяти символов и закодируем их полученным кодом Фано:

a₄ a₆ a₈ a₁₀ a₁₂

2122200222122122221

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

Так как код является троичным, то основание кода . Отсюда следует:

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

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



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

Рассчитаем среднее количество символов, приходящихся на одно сообщение, по формуле (2.9) лекции:

где P_s - вероятность появления события;

m - количество символов в коде.

Количество символов в коде представлено в таблице 14.

Таблица 14

Сообщение	Вероятность события Ps	Количество символов в коде ms
a1	0,38	1
a2	0,12	2
a3	0,071	3
a4	0,21	2
a5	0,013	5
a6	0,004	5
a7	0,012	5
a8	0,03	4
a9	0,0211	5
a10	0,1	3
a11	0,019	5
a12	0,0199	5



Найдем эффективность кода по формуле:

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

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

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

Задача №4.3

Дискретный источник U выдает независимые равновероятные сообщения с объемом алфавита N=20 со скоростью V_c=3200 сообщений в секунду. Оценить, возможна ли безошибочная передача сообщений источника по двоичному симметричному каналу, вероятность ошибки в котором p=0,05, а скорость передачи канальных символов V_k не может превышать V_c более чем в n=3 раз. В случае отсутствия такой возможности оценить минимально неизбежные потери информации в единицу времени.

Решение:

В соответствие с теоремой Шеннона безошибочная передача информации возможна при условии (2.15) лекции:

, где

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

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

В соответствии с формулой (1.28) лекции пропускная способность двоичного симметричного канала равна:

, где

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

В соответствии со вторым утверждением прямой теоремы минимальная потеря информации в единицу времени составляет:

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

Ответ: Безошибочная передача сообщений источника невозможна, .

Задача №4.33

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

Решение:

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

Откуда находим k:

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

, где

I_k - единичная матрица, содержащая информационные символы,

R_k,r - прямоугольная матрица, составленная из проверочных симвлов.

Построим матрицу I, где k=6.

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

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

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

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

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

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

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



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

Проверочная матрица H имеет размерность (n-k, k) и имеет следующий вид:

, где

R^T - транспонированная матрица R,

I - единичная матрица.

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

Кодовая комбинация представляет k - информационных и r - проверочных символов:

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

Найдем на приеме и исправим эту ошибку. Для этого:

а) по принятым информационным найдем проверочные разряды:

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

в) строим проверочную матрицу и отслеживаем в ней найденную комбинацию:

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

Код является кодом Хемминга, если будут выполняться следующие условия:

, (10,6)

n=10, k=6, r=4 - разработанный код

Полученная матрица G имеет разрядность (10,6), которая не удовлетворяет данному условию. Значит, данный код не является кодом Хемминга.

Заключение

сигнал кодирование информационный дискретный

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

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

Размещено на Allbest.ru