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

Введение

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

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

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

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

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

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

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

Задача № 1.26

Распределение вероятностей дискретной случайной величины имеет вид: p(x₁)=0,362 133; 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,17 867. Определить число 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

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

Решение:

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

Таблица 2

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

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

Потенциальный минимум будем искать по формуле (2.3) лекции Так как код является двоичным, то основание кода. Отсюда следует:

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

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

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

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

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

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

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

Таблица 3

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

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

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

Задача № 3.33

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

Таблица 4

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

Решение:

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

Таблица 5

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

a₁ a₂ a₃ a₄ a₅

Потенциальный минимум будем искать по формуле (2.3) лекции Так как код является троичным, то основание кода. Отсюда следует:

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

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

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

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

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

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

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

Таблица 6

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

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

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

Задача № 3.63

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

Таблица 7

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

Решение:

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

Таблица 8

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

Рисунок 3.1

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

Таблица 9

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

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

Потенциальный минимум будем искать по формуле (2.3) лекции Так как код является двоичным, то основание кода. Отсюда следует:

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

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

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

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

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

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

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

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

Таблица 10

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

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

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

Задача № 3.93

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

Таблица 11

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

Решение:

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

Таблица 12

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

Рисунок 3.2

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

Таблица 13

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

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

Потенциальный минимум будем искать по формуле (2.3) лекции Так как код является троичным, то основание кода. Отсюда следует:

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

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

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

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

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

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

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

Таблица 14

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

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

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

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), которая не удовлетворяет данному условию. Значит, данный код не является кодом Хемминга.

Заключение

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

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