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

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

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

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

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

Содержание

Реферат

Введение

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 значений случайной величины, при которых энтропия Hp(X) равномерного распределения будет равна энтропии H(X) заданного распределения.

Решение:

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

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

Из условия, что

находим:

Ответ: при объеме алфавита n = 7, энтропия Hp(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

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

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

Решение:

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

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

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

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

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

По формуле (1.9) лекции найдем

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

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

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

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

2.1 Задача № 2.24

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

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

Решение:

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

Рис. 2.1

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

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

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

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

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

;

Ответ: априорные вероятности в данном канале равны: P(U1/Z1) = 0,96; P(U1/Z2) = 0,23; P(U2/Z1) = 0,04; P(U2/Z2) = 0,77.

2.2 Задача № 2.58

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

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

Решение:

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

Скорость рассчитаем по формуле

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

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

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

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

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

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

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

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

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

3.1 Задача № 3.24

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

А1	А2	А3	А4	А5	А6	А7	А8	А9	А10	А11	А12
0,088	0,065	0,035	0,062	0,06	0,059	0,097	0,3	0,068	0,044	0,054	0,122

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

Решение:

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

А8	0,3	0
А12	0,122	10
А7	0,097	100
А1	0,088	101
А9	0,068	110
А2	0,065	1110
А4	0,062	11110
А6	0,059	111110
А11	0,054	1111110
А10	0,044	1111110
А3	0,035	11111110
А5	0,006	11111111

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

А9А3А5А7А4

110111111101111111110011110.

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

;

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

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

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

;

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

, где

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

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

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

P1 = 0,088	n1 = 3
P2 = 0,065	n2 = 4
P3 = 0,035	n3 = 8
P4 = 0,062	n4 = 5
P5 = 0,006	n5 = 8
P6 = 0,059	n6 = 6
P7 = 0,097	n7 = 3
P8 = 0,3	n8 = 1
P9 = 0,068	n9 = 3
P10 = 0,044	n10 = 7
P11 = 0,054	n11 = 7
P12 = 0,122	n12 = 2

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

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

3.2 Задача № 3.54

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

А1	А2	А3	А4	А5	А6	А7	А8	А9	А10	А11	А12
0,082	0,122	0,503	0,04	0,012	0,002	0,005	0,034	0,124	0,006	0,0395	0,0305

Решение:

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

А3	0,503	0
А9	0,124	10
А2	0,122	210
A1	0,082	3210
А4	0,04	43210
А11	0,0395	443210
А8	0,034	4443210
А12	0,0305	44443210
А5	0,012	44444321
А10	0,006	44444432
А7	0,005	44444443
А6	0,002	44444444

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

А1А2А3А4А5

321021004321044444321

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

;

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

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

;

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

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

, где

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

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

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

P1 = 0,82	n1 = 4
P2 = 0,122	n2 = 3
P3 = 0,503	n3 = 1
P4 = 0,004	n4 = 5
P5 = 0,012	n5 = 8
P6 = 0,002	n6 = 8
P7 = 0,005	n7 = 8
P8 = 0,034	n8 = 7
P9 = 0,124	n9 = 2
P10 = 0,006	n10 = 8
P11 = 0,0395	n11 = 6
P12 = 0,0305	n12 = 8

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

3.3 Задача № 3.84

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

А1	А2	А3	А4	А5	А6	А7	А8	А9	А10	А11	А12
0,082	0,122	0,503	0,04	0,012	0,002	0,005	0,034	0,124	0,006	0,0395	0,0305

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

Решение:

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

А3	0,503	0,503	0,503	0,503	0,503	0,503	0,503	0,503	0,503	0,503	0,503	1
А9	0,124	0,124	0,124	0,124	0,124	0,124	0,124	0,1555	0,2175	0,2795	0,497
А2	0,122	0,122	0,122	0,122	0,122	0,122	0,122	0,124	0,1555	0,2175
A1	0,082	0,082	0,082	0,082	0,082	0,082	0,0955	0,122	0,124
А4	0,04	0,04	0,04	0,04	0,0555	0,0735	0,082	0,0955
А11	0,0395	0,0395	0,0395	0,0395	0,04	0,0555	0,0735
А8	0,034	0,034	0,034	0,034	0,0395	0,04
А12	0,0305	0,0305	0,0305	0,0305	0,034
А5	0,012	0,012	0,013	0,025
А10	0,006	0,007	0,012
А7	0,005	0,006
А6	0,002

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

Рис. 3.1

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

P1 = 0,82	0111	n1 = 4
P2 = 0,122	001	n2 = 3
P3 = 0,503	1	n3 = 1
P4 = 0,004	0000	n4 = 4
P5 = 0,012	000100	n5 = 6
P6 = 0,002	00010110	n6 = 8
P7 = 0,005	00010111	n7 = 8
P8 = 0,034	01100	n8 = 5
P9 = 0,124	010	n9 = 3
P10 = 0,006	0001010	n10 = 7
P11 = 0,0395	01101	n11 = 5
P12 = 0,0305	00011	n12 = 5

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

А1А2А7А6А4

011100100010111000101100000.

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

;

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

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

;

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

, где

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

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

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

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

3.4 Задачи № 3.114

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

А1	А2	А3	А4	А5	А6	А7	А8	А9	А10	А11	А12
0,082	0,122	0,503	0,04	0,012	0,002	0,005	0,034	0,124	0,006	0,0395	0,0305

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

Решение:

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

А3	0,503	0,503	0,503	1
А9	0,124	0,124	0,251
А2	0,122	0,122	0,124
A1	0,082	0,082	0,122
А4	0,04	0,0555
А11	0,0395	0,04
А8	0,034	0,0395
А12	0,0305	0,034
А5	0,012
А10	0,006
А7	0,005
А6	0,002

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

Рис.3.2

P1 = 0,82	24	n1 = 2
P2 = 0,122	0	n2 = 1
P3 = 0,503	3	n3 = 1
P4 = 0,004	22	n4 = 2
P5 = 0,012	233	n5 = 3
P6 = 0,002	230	n6 = 3
P7 = 0,005	231	n7 = 3
P8 = 0,034	20	n8 = 2
P9 = 0,124	1	n9 = 1
P10 = 0,006	232	n10 = 3
P11 = 0,0395	21	n11 = 2
P12 = 0,0305	234	n12 = 3

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

А8А7А6А5А4

2023023023322.

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

;

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

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

;

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

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

, где

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

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

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

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

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

4.1 Задача № 4.24

Определить избыточного оптимального по Шеннону кода (существование которого утверждается теоремой для канала с шумом) с объемом алфавита М =3 и средним количеством символов, переданных в единицу времени - Vk, предназначенного для безошибочной передачи информации по каналу с пропускной способностью С. Найти минимально возможную избыточность оптимального кода для симметричного канала с вероятностью ошибки Р = 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 11000100001.

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

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

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

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

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

j = 1:

j = 2:

j =3:

j = 4:

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

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

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

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

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

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

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

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

[1001][1100] = [0101].

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

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

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

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

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

Заключение

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

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

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

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

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